Binary Tree Postorder traversal

public class Solution {
    public ArrayList<Integer> postorderTraversal(TreeNode root) {
        ArrayList<Integer> lst = new ArrayList<Integer> ();  
        if (root == null) {
            return lst;  
        }
        Stack<TreeNode> stack = new Stack<TreeNode> (); 
        stack.push(root);
        
        /*
         * There are 3 cases discussed: 
         * (1) root --> left or root --> right; 
         * (2) left --> root; 
         * (3) right --> root; 
         * We need a variable to store the previous root. 
         * We also need a variable to store the current node.  
         */
        TreeNode pre = null;
        while (!stack.empty()) {
            TreeNode cur = stack.peek(); 
            
            if (pre == null || pre.left == cur || pre.right == cur) {
                //prev == null is the situation for the root node
                if (cur.left != null) {
                    stack.push (cur.left); 
                } else if (cur.right != null) {
                    stack.push (cur.right); 
                } else { 
                    stack.pop(); 
                    lst.add(cur.val);
                }
                
            }else if (cur.left == pre) {
                if (cur.right != null) {
                    stack.push (cur.right); 
                } else {
                    stack.pop();
                    lst.add(cur.val); 
                }
            }else if (cur.right == pre) {
                stack.pop(); 
                lst.add(cur.val);
            }
            //update pre: 
            pre = cur; 
        }
        
        return lst; 
    }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s