145. Binary Tree Postorder Traversal

Whatever preorder, inorder or postorder, we need to traverse under the help of stack.

1. postorder under the help of null left node

According the definition of postorder, the traverse order is left -> right -> root. Whenever a node is pushed into the stack, we iteratively push the left node into the stack until the left node is null. In order to process the right node, we push the null left node into the stack, too. When a node is popped out of the stack. We judge whether it is the left node of the top element. If so, we push the non-null right node of top element into the stack. If not, then the popped node is the right node of top element which means the left part and right part of the top element have been both visited. As we can see, the key of the solution is the null left node.

public List<Integer> postorderTraversal(TreeNode root) {
    List<Integer> resultList = new ArrayList<Integer>();
    Stack<TreeNode> stack = new Stack<TreeNode>();
    TreeNode current = root;
    while( current != null ) { // iteratively push left node into stack
        stack.push(current);
        current = current.left;
    }
    stack.push(current); // null left node also need to be pushed into stack
    while( !stack.isEmpty() ) {
        current = stack.pop();
        if( current != null )
            resultList.add(current.val);
        if( !stack.isEmpty() && current == stack.peek().left && stack.peek().right != null) { // traverse right part
            TreeNode left = stack.peek().right;
            while( left != null ) {
                stack.push(left);    
                left = left.left;
            }
            stack.push(left);
        }
    }
    return resultList;
}

2. preorder which traverse right node first

This solution is actually a preorder traverse where the order is root -> right -> left. Each time a node is poped out of the stack, we put its val to the head of list instead of tail.

public List<Integer> postorderTraversal(TreeNode root) {
    List<Integer> resultList = new ArrayList<Integer>();
    Stack<TreeNode> stack = new Stack<TreeNode>();
    if( root != null )
        stack.push(root);
    while( !stack.isEmpty() ) {
        TreeNode current = stack.pop();
        resultList.add(0, current.val);
        if( current.left != null )
            stack.push(current.left);
        if( current.right != null )
            stack.push(current.right);
    }
    return resultList;
}