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

Analysis

See reference

Code

public class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        if (root==null) return res;

        Stack<TreeNode> st1 = new Stack<TreeNode>();
        Stack<TreeNode> st2 = new Stack<TreeNode>();
        st1.push(root);

        while (!st1.empty()){
            TreeNode tmp = st1.peek();
            st2.push(st1.pop());
            if (tmp.left!=null) {st1.push(tmp.left);}
            if (tmp.right!=null) {st1.push(tmp.right);}
        }

        while (!st2.empty()){
            res.add(st2.pop().val);
        }

        return res;
    }
}

Reference

• Yu: clear image and analysis on non-recursive post order traversal with c++ code