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?
分析¶
这道题目和144. Binary Tree Preorder Traversal一摸一样,给出三种方案:
有帮助函数的递归,省去了反复要生成List<Integer>
.
public List<Integer> postorderTraversal(TreeNode root) { List<Integer> list = new ArrayList<>(); postorderTraversalHelper(root, list); return list; } private void postorderTraversalHelper(TreeNode root, List<Integer> list) { if (root == null) return; postorderTraversalHelper(root.left, list); postorderTraversalHelper(root.right, list); list.add(root.val); }
直接递归:
public List<Integer> postorderTraversal(TreeNode root) { List<Integer> list = new ArrayList<>(); if (root == null) return list; list.addAll(postorderTraversal(root.left)); list.addAll(postorderTraversal(root.right)); list.add(root.val); return list; }
迭代:
public List<Integer> postorderTraversal(TreeNode root) { List<Integer> list = new ArrayList<>(); Stack<TreeNode> stack = new Stack<>(); stack.push(root); while(!stack.isEmpty()) { TreeNode cur = stack.pop(); if (cur != null) { list.add(0, cur.val); stack.push(cur.left); stack.push(cur.right); } } return list; }
近期评论