[Leetcode] Binary Tree Postorder Traversal II

The follow up for the first post about postorder traversal.

In the first post, I introduced how to use Morris iteration to implement postorder traversal of a given binary tree. However it is too complicate and not easy to code during an interview. Here, I introduce another two ways to do a postorder traversal iteratively.

The first method is to use two stacks.

1. Push the root node to the first stack.
2. Pop a node from the first stack, and push it to the second stack.
3. Then push its left child followed by its right child to the first stack.
4. Repeat step 2) and 3) until the first stack is empty.
5. Once done, the second stack would have all the nodes ready to be traversed in post-order. Pop off the nodes from the second stack one by one and you’re done.

    
    List<Integer> list = new ArrayList<Integer>();
    
    public List<Integer> postorderTraversal(TreeNode root) {
        if(root == null)
   return list; // corner case when root is null
  
  Stack<TreeNode> stack1 = new Stack<TreeNode>();
  Stack<TreeNode> stack2 = new Stack<TreeNode>();
  stack1.push(root);
  while(stack1.size() != 0) {
   TreeNode cur = stack1.pop();
   if(cur.left != null)
    stack1.push(cur.left);
   if(cur.right != null)
    stack1.push(cur.right);
   stack2.push(cur);
  }
  while(stack2.size() != 0) 
   list.add(stack2.pop().val);
  return list;
    }

Another way is just use one stack, and use a node to record the prior visited node. According to the type of the current node(leaf, nonleaf with only left or right child, nonleaf with both children) to perform differently.

1. Each time we pick the top of the stack and check
• if it is a leaf node, then print it
• if it is a node with only left child, if pre = left child, then we know we have finish visiting the left child, print it; otherwise, the left child has not been visited yet, we push the current node pack and push the left child into stack
• if it is a node with only right child, similar with the prior one
• if it is a node with both children
• if pre = left child, we know we finish the left child and we need to continue with right child, so push itself and right child into stack
• if pre = right child, we know we have finished both child, print it
• else we have not visited any child, we push itself and left child into stack
2. Update the pre node when we print something out

 public static void postorder(TreeNode root) {
  if(root == null)
   return ; // corner case when root is null
  
  Stack<TreeNode> stack = new Stack<TreeNode>();
  TreeNode pre = null, cur = null;
  stack.push(root);
  while(stack.size() != 0) {
   cur = stack.pop();
   if(cur.left == null && cur.right == null) {
    System.out.println(cur.val);
    pre = cur;
   }
   else if(cur.left != null && cur.right == null) {
    if(pre == cur.left) {
     System.out.println(cur.val);
     pre = cur;
    }
    else {
     stack.push(cur);
     stack.push(cur.left);
    }
   }
   else if(cur.left == null && cur.right != null) {
    if(pre == cur.right) {
     System.out.println(cur.val);
     pre = cur;
    }
    else {
     stack.push(cur);
     stack.push(cur.right);
    }
   }
   else {
    if(pre == cur.left) {
     stack.push(cur);
     stack.push(cur.right);
    }
    else if(pre == cur.right) {
     System.out.println(cur.val);
     pre = cur;
    }
    else {
     stack.push(cur);
     stack.push(cur.left);
    }
   }
  }
 }

My implementation is somehow redundant. Here is a better implementation but a little harder to understand.http://leetcode.com/2010/10/binary-tree-post-order-traversal.html