Given a binary tree, return the postorder traversal of its nodes' values.
For example:
Given binary tree {1,#,2,3},
1 \ 2 / 3
return [3,2,1].
Note: Recursive solution is trivial, could you do it iteratively?
前序永远是
【根】【左子树】【右子树】
中序永远是
【左子树】【根】【右子树】
后序永远是
【左子树】【右子树】【根】
1. recursion
public class Solution { ArrayList<Integer> list = new ArrayList<Integer>(); public ArrayList<Integer> postorderTraversal(TreeNode root) { if(root == null) return list; if(root.left != null) postorderTraversal(root.left); if(root.right !=null) postorderTraversal(root.right); list.add(root.val); return list; } }
2.iterative
public class Solution { public ArrayList<Integer> postorderTraversal(TreeNode root) { ArrayList<Integer> list = new ArrayList<Integer>(); if(root == null) return list; Stack<TreeNode> stack = new Stack<TreeNode>(); stack.push(root); TreeNode prev = null; while(!stack.isEmpty()){ TreeNode cur = stack.peek(); // go down the tree. //check if current node is leaf, if so, process it and pop stack, //otherwise, keep going down if(prev == null||prev.left == cur || prev.right == cur){ if(cur.left != null) stack.push(cur.left); else if(cur.right !=null) stack.push(cur.right); else{ stack.pop(); list.add(cur.val);} } //go up the tree from left node //need to check if there is a right child //if yes, push it to stack //otherwise, process parent and pop stack else if(cur.left == prev){ if(cur.right != null) stack.push(cur.right); else{ stack.pop(); list.add(cur.val); } } else if(cur.right == prev){ stack.pop(); list.add(cur.val); } prev = cur; } return list; } }
learned: prev works as node, do stack push root-> left -> right; traverse the tree to leftmost first, then go back to leftmost parent, then to parent's right
public class Solution { public List<Integer> postorderTraversal(TreeNode root) { List<Integer> list = new LinkedList<Integer>(); Stack<TreeNode> stack = new Stack<TreeNode>(); if(root == null) return list; while(root != null || !stack.isEmpty()) { // first to get the most left child while(root != null) { stack.push(root); if(root.left != null) { root = root.left; } else { root = root.right; } } //Then add it to the list if(!stack.isEmpty()) { root = stack.pop(); list.add(root.val); } //if the right tree finishes traversal, then get the root from the stack while(!stack.isEmpty() && stack.peek().right == root) { root = stack.pop(); list.add(root.val); } //turn from the left tree to the right tree under the same root if(!stack.isEmpty()) { root = stack.peek().right; } else { root = null; } } return list; } }
public class Solution { public List<Integer> postorderTraversal(TreeNode root) { List<Integer> list = new LinkedList<Integer>(); Stack<TreeNode> stack = new Stack<TreeNode>(); Stack<TreeNode> output = new Stack<TreeNode>(); if(root == null) return list; stack.push(root); while(!stack.isEmpty()) { TreeNode cur = stack.pop(); output.push(cur); if(cur.left != null){ stack.push(cur.left); } if(cur.right != null){ stack.push(cur.right); } } while(!output.isEmpty()){ list.add(output.pop().val); } return list; } }