Given a binary tree, return the postorder traversal of its nodes' values.
Example
Given binary tree {1,#,2,3},
1
\
2
/
3
return [3,2,1].
Challenge
Can you do it without recursion?
思路
解法一:
Traverse
Code
/** * Definition of TreeNode: * public class TreeNode { * public int val; * public TreeNode left, right; * public TreeNode(int val) { * this.val = val; * this.left = this.right = null; * } * } */ public class Solution { /** * @param root: The root of binary tree. * @return: Postorder in ArrayList which contains node values. */ public ArrayList<Integer> postorderTraversal(TreeNode root) { // write your code here ArrayList<Integer> result = new ArrayList<>(); traverse(root, result); return result; } public void traverse(TreeNode root, ArrayList<Integer> result) { if (root == null) { return; } traverse(root.left, result); traverse(root.right, result); result.add(root.val); } }
解法二:
Divide & Conquer
Code
/** * Definition of TreeNode: * public class TreeNode { * public int val; * public TreeNode left, right; * public TreeNode(int val) { * this.val = val; * this.left = this.right = null; * } * } */ public class Solution { /** * @param root: The root of binary tree. * @return: Postorder in ArrayList which contains node values. */ public ArrayList<Integer> postorderTraversal(TreeNode root) { // write your code here ArrayList<Integer> result = new ArrayList<>(); if (root == null) { return result; } ArrayList<Integer> left = postorderTraversal(root.left); ArrayList<Integer> right = postorderTraversal(root.right); result.addAll(left); result.addAll(right); result.add(root.val); return result; } }
解法三:
Iterative
反方向pre-order。然后把答案reverse一下。
Code
Code
/** * Definition of TreeNode: * public class TreeNode { * public int val; * public TreeNode left, right; * public TreeNode(int val) { * this.val = val; * this.left = this.right = null; * } * } */ public class Solution { /** * @param root: The root of binary tree. * @return: Postorder in ArrayList which contains node values. */ public ArrayList<Integer> postorderTraversal(TreeNode root) { // write your code here ArrayList<Integer> result = new ArrayList<>(); if (root == null) { return result; } Stack<TreeNode> stack = new Stack<>(); stack.push(root); while (!stack.isEmpty()) { TreeNode node = stack.pop(); result.add(node.val); if (node.left != null) { stack.push(node.left); } if (node.right != null) { stack.push(node.right); } } Collections.reverse(result); return result; } }
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public List<Integer> postorderTraversal(TreeNode root) { List<Integer> result = new ArrayList<>(); if (root == null) { return result; } Stack<TreeNode> stack = new Stack<>(); TreeNode prev = null; stack.push(root); while (!stack.isEmpty()) { TreeNode node = stack.peek(); if (prev == null || prev.left == node || prev.right == node) { if (node.left != null) { stack.push(node.left); } else if (node.right != null) { stack.push(node.right); } } else if (node.left == prev) { if (node.right != null) { stack.push(node.right); } } else { result.add(node.val); stack.pop(); } prev = node; } return result; } }