145. Binary Tree Postorder Traversal Leetcode Java

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?

Solution:

Like other 2 traversals, 3 solutions will be presented.
All traversal problems:
94.   Binary Tree Inorder Traversal
144. Binary Tree Preorder Traversal
145. Binary Tree Postorder Traversal

1st, the trivial one: recursive solution

  public List<Integer> postorderTraversal(TreeNode root) {  
    List<Integer> res=new ArrayList<Integer>();  
    helper(root,res);  
    return res;  
   }  
   public void helper(TreeNode root, List<Integer> res){  
     if(root==null) return;  
     helper(root.left,res);  
     helper(root.right,res);  
     res.add(root.val);  
   }  

2nd, Iteration with extra space
It is a little bit more tricky than other two cases, we have to push both left and right to stack. Obviously, if current node's left is not null, we push its left, if cur's right is not null, we have to check if the cur'right has been processed, if so, output cur.

    public List<Integer> postorderTraversal(TreeNode root) {  
    List<Integer> res=new ArrayList<Integer>();  
    if(root==null) return res;  
    Stack<TreeNode> st=new Stack<TreeNode>();  
    TreeNode pre=null;  
    while(root!=null || !st.isEmpty()){  
      if(root!=null){  
        st.push(root);  
        root=root.left;  
      }  
      else{  
        if(st.peek().right==null || st.peek().right==pre){  
          pre=st.pop();  
          res.add(pre.val);  
        }  
        else root=st.peek().right;  
      }  
    }  
    return res;  
   }  

3rd, Iteration with no extra space: Morris transverse using threading.
It is much more complicated than other two cases.
First trick is to create a dummy node and set dummy.left=root, which will avoid taking special case when there root only have right subtree.
Basic steps:
if the cur.left==null, set cur=cur.right
If the cur.left!=null, find the right-most child of cur.left, 
     if cur.left.rightmost.right==null, which means, the current node and cur.left has not been visited, and the rightmost node is the predecessor of cur node, set rightmost.right=cur and cur=cur.left
     if cur.left.rightmost.right=cur, which means the current node has been visited, and cur.left has been processed, so reversely output cur.left.val -> pre.val, restore the tree by set rightmost.right=null, and set cur=cur.right, reverse it back after adding to result list;

Notice that: each edge will be only visited at most twice, so the time complexity still O(2*E)=O(4*V)=O(V). 

 public List<Integer> postorderTraversal(TreeNode root) {  
    List<Integer> res=new ArrayList<Integer>();  
    if(root==null) return res;  
    TreeNode preDummy=new TreeNode(0);  
    preDummy.left=root;  
    TreeNode cur=preDummy;  
    while(cur!=null){  
      if(cur.left==null) cur=cur.right;  
      else{  
        TreeNode pre=cur.left;  
        while(pre.right!=null && pre.right!=cur) pre=pre.right;  
        if(pre.right==null){  
          pre.right=cur;  
          cur=cur.left;  
        }  
        else{  
          pre.right=null;  
          TreeNode head=reverse(cur.left);  
          TreeNode temp=head;  
          while(temp!=null){  
            res.add(temp.val);  
            temp=temp.right;  
          }  
          reverse(head);  
          cur=cur.right;  
        }  
      }  
    }  
    preDummy.left=null;  
    return res;  
   }  
   public TreeNode reverse(TreeNode start){  
     TreeNode head=start;  
     TreeNode pre=start;  
     while(pre.right!=null){  
       TreeNode cur=pre.right;  
       pre.right=cur.right;  
       cur.right=head;  
       head=cur;  
     }  
     return head;  
   }