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

Note: Recursive solution is trivial, could you do it iteratively?

Recursive Solution:

/**
 * 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> result = new ArrayList<Integer>();
        
        postorderTraversal(root, result);
        
        return result;
    }
    
    private void postorderTraversal(TreeNode node, ArrayList<Integer> result) {
        if (node == null) return;
        
        postorderTraversal(node.left, result);
        postorderTraversal(node.right, result);
        result.add(node.val);
    }
}

Iterative Solution:
The idea in iterative solution is still using a stack. We use two pointers, one points to the current node which is peeked from the stack, the other points to the node just visited before. When we goes down, the current pointer is below of the previous pointer. And we push nodes into the stack. If the node is a leaf, we pop it from the stack, and go up. In this case, the current pointer is above of the previous pointer. In this case, we have two cases to handle. One case is we go from the left child. Then we should check the right child. If it has right child, push it down to the stack; else pop the node. If we go from the right child, which means we have post-order traversed its left child and right child, then its parent should be pop out. 

Code (Java):

/**
 * 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> result = new ArrayList<Integer>();
        if (root == null) return result;
        
        Stack<TreeNode> stack = new Stack<TreeNode>();
        
        stack.push(root);
        TreeNode prev = null;
        
        while (!stack.empty()) {
            TreeNode curr = stack.peek();
            if (prev == null || curr == prev.left || curr == prev.right) {
                if (curr.left != null) {
                    stack.push(curr.left);
                } else if (curr.right != null) {
                    stack.push(curr.right);
                } else {
                    stack.pop();
                    result.add(curr.val);
                }
            } else if (prev == curr.left) {
                if (curr.right != null) {
                    stack.push(curr.right);
                } else {
                    stack.pop();
                    result.add(curr.val);
                }
            }else if (prev == curr.right) {
                stack.pop();
                result.add(curr.val);
            }
            
            prev = curr;
        }
        
        return result;
    }
}

Summary:
In this post, we learned the postorder binary tree traversal. The iterative approach used two pointers. One points to the current node, one to the last visited node. 

So far we have learned the three different types of DFS: preorder, inorder and postorder. All of the three traversals used a stack to store the intermediate nodes. In the preorder traversal, we just used a stack without pointers. In the inorder traversal, we use one pointer pointing to the current node. In the postorder traversal, we use two pointers, one points to the current node, while the other one points to the last visited node. 

All of the three traversals in iterative way is a bit of tricky. Make sure you understand and be very familiar with the method.