摘要:按順序放入,正好方面是從到,順序方面是從最右到最左,因為是先入后出。這樣最后一下就是先左后右,先子后根。
590. N-ary Tree Postorder Traversal Problem
Given an n-ary tree, return the postorder traversal of its nodes" values.
For example, given a 3-ary tree:
Return its postorder traversal as: [5,6,3,2,4,1].
Note: Recursive solution is trivial, could you do it iteratively?
class Solution { public ListSolution (Iteration)postorder(Node root) { List res = new ArrayList<>(); helper(root, res); return res; } private void helper(Node root, List res) { if (root == null) return; if (root.children != null) { for (Node child: root.children) { helper(child, res); } } res.add(root.val); } }
按順序放入stack,正好level方面是從root到leaves,順序方面是從最右到最左,因為stack是先入后出。這樣最后reverse一下就是先左后右,先子后根。
巧妙。
class Solution { public List145. Binary Tree Postorder Traversalpostorder(Node root) { List res = new ArrayList<>(); if (root == null) return res; Stack stack = new Stack<>(); stack.push(root); while (!stack.isEmpty()) { Node node = stack.pop(); res.add(node.val); for (Node child: node.children) { stack.push(child); } } Collections.reverse(res); return res; } }
Given a binary tree, return the postorder traversal of its nodes" values.
Example:
Input: [1,null,2,3]
1 2 / 3
Output: [3,2,1]
Follow up: Recursive solution is trivial, could you do it iteratively?
class Solution { public ListSolution (Recursion)postorderTraversal(TreeNode root) { List res = new ArrayList<>(); if (root == null) return res; Stack stack = new Stack<>(); stack.push(root); while (!stack.isEmpty()) { TreeNode node = stack.pop(); res.add(node.val); if (node.left != null) stack.push(node.left); if (node.right != null) stack.push(node.right); } Collections.reverse(res); return res; } }
class Solution { public ListpostorderTraversal(TreeNode root) { List res = new ArrayList<>(); helper(root, res); return res; } private void helper(TreeNode node, List res) { if (node == null) return; if (node.left != null) helper(node.left, res); if (node.right != null) helper(node.right, res); res.add(node.val); } }
文章版權(quán)歸作者所有,未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址:http://m.specialneedsforspecialkids.com/yun/77376.html
摘要:題目鏈接題目分析后序遍歷,這題也是比較基礎的題目了。思路先遍歷子節(jié)點,再遍歷根節(jié)點。最終代碼若覺得本文章對你有用,歡迎用愛發(fā)電資助。 D44 590. N-ary Tree Postorder Traversal 題目鏈接 590. N-ary Tree Postorder Traversal 題目分析 后序遍歷,這題也是比較基礎的題目了。 思路 先遍歷子節(jié)點,再遍歷根節(jié)點。 最終代碼...
589. N-ary Tree Preorder Traversal Given an n-ary tree, return the preorder traversal of its nodes values.For example, given a 3-ary tree:showImg(https://segmentfault.com/img/bVbhKkv?w=781&h=502);Retu...
429. N-ary Tree Level Order Traversal Given an n-ary tree, return the level order traversal of its nodes values. (ie, from left to right, level by level). For example, given a 3-ary tree:showImg(https...
摘要:題目要求對叉樹進行水平遍歷,并輸出每一行遍歷的結(jié)果。因此無需再用隊列來額外存儲每一行的水平遍歷,可以直接通過遞歸將遍歷結(jié)果插入到相應行的結(jié)果集中。 題目要求 Given an n-ary tree, return the level order traversal of its nodes values. (ie, from left to right, level by level)...
摘要:題目鏈接題目分析按層遍歷叉樹。思路以層數(shù)為鍵,塞入當前節(jié)點的值。最終代碼若覺得本文章對你有用,歡迎用愛發(fā)電資助。 D55 429. N-ary Tree Level Order Traversal 題目鏈接 429. N-ary Tree Level Order Traversal 題目分析 按層遍歷N叉樹。 思路 以層數(shù)為鍵,塞入當前節(jié)點的值。 遞歸遍歷即可。 最終代碼
閱讀 1763·2021-09-23 11:34
閱讀 2485·2021-09-22 15:45
閱讀 13011·2021-09-22 15:07
閱讀 2250·2021-09-02 15:40
閱讀 4154·2021-07-29 14:48
閱讀 1087·2019-08-30 15:55
閱讀 3252·2019-08-30 15:55
閱讀 2199·2019-08-30 15:55