Binary Tree - Binary Tree Postorder Traversal

So recursion is a good friend, but not for memory.

The tough part is to figure out/watch actually the result list is a pop process for a second stack which is defined as result below. The first stack is used to hold cur node, and after one loop it will be popped out and push into the result … watch it works!!! two stacks!!!! my way to observe it was to write down and analyze the number… which made more sense to me… but smart guy should be able to get it from the tree directly.


/**
 * 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> postOrder = new ArrayList<Integer>();
        if(root == null){
            return postOrder;
        }
        Stack<TreeNode> process = new Stack<TreeNode>();
        process.push(root);
        Stack<TreeNode> result = new Stack<TreeNode>();
        while(!process.isEmpty()){
            TreeNode processing = process.pop();
            if(processing.left != null){
                process.push(processing.left);
            }
            if(processing.right != null){
                process.push(processing.right);
            }
            result.push(processing);
        }
        while(!result.isEmpty()){
            postOrder.add(result.pop().val);
        }
        return postOrder;
    }
}