Binary Tree Postorder Traversal

Source

• leetcode: Binary Tree Postorder Traversal

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].

Java

/* 
Postorder is to visit nodes in a left-right-root order, recursively.Recall that preorder is root-left-right.
If we visit the nodes in a "mirrored preorder", that is, root-right-left, and store the values in a stack.
After we finish the traversal, pop out values in the stack would give us left-right-root,
which is exactly a postorder traversal! 
*/ 
public class Solution {
    public ArrayList<Integer> postorderTraversal(TreeNode root) {    
        List<Integer> result = new ArrayList<Integer>();
        Stack<TreeNode> stack = new Stack<TreeNode>();

        TreeNode cur = root;
        while(cur!=null){
            result.add(cur.val);
            stack.push(cur);
            cur=cur.right;
        }

        while(!stack.isEmpty()){
            cur = stack.pop().left;
            while(cur!=null){
                result.add(cur.val);
                stack.push(cur);
                cur=cur.right;
            }
        }
        Collections.reverse(result);
        return result;  
    }    
}