wayetan
12/30/2013 - 5:14 AM

## Binary Tree Postorder Traversal

Binary Tree Postorder Traversal

``````public class Solution {
public ArrayList<Integer> postorderTraversal(TreeNode root) {
ArrayList<Integer> res = new ArrayList<Integer>();
if(root == null)
return res;
Stack<TreeNode> s = new Stack<TreeNode>();
Stack<TreeNode> output = new Stack<TreeNode>();
s.push(root);
while(!s.isEmpty()){
TreeNode curr = s.pop();
output.push(curr);
if(curr.left != null)
s.push(curr.left);
if(curr.right != null)
s.push(curr.right);
}
while(!output.isEmpty()){
}
return res;
}
}``````
``````/**
* 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?
*/

/**
* Definition for binary tree
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/

public class Solution {
public ArrayList<Integer> postorderTraversal(TreeNode root) {
ArrayList<Integer> res = new ArrayList<Integer>();
if(root == null)
return res;
Stack<TreeNode> s = new Stack<TreeNode>();
s.push(root);
TreeNode prev = null;
while(!s.isEmpty()){
TreeNode curr = s.peek();
if(prev == null || prev.left == curr || prev.right == curr){
// traverse from top to bottom, and if curr has left child or right child, push into the stack; otherwise, pop out.
if(curr.left != null)
s.push(curr.left);
else if(curr.right != null)
s.push(curr.right);
}else if(curr.left == prev){
if(curr.right != null)
s.push(curr.right);
}else{