94. Binary Tree Inorder Traversal Leetcode Java

Given a binary tree, return the inorder traversal of its nodes' values.

For example:
Given binary tree {1,#,2,3},

   1
    \
     2
    /
   3

return [1,3,2].

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

Solution:

All traversal problems:

94.   Binary Tree Inorder Traversal

144. Binary Tree Preorder Traversal

145. Binary Tree Postorder Traversal

I will present total 3 solutions.

1st, the trivial one: recursive solution

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

2nd, Iteration with extra space
Use a stack to record the preceding parent node, so when we finish the left node, and we can find its parent node/ preceding node.

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

3rd, Iteration with no extra space: Morris in order transverse using threading
See these two wiki pages for more information: Morris in order traversal using threading ;
Threaded binary tree. 
Basic idea is to thread the binary tree by creating the links to the in-order predecessor.
After the thread is created, we can do the in-order traversal and also revert the change to original tree during the traversal.
Basic steps:
if the cur.left==null, add cur.val into result list, 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 output cur.val, restore the tree by set rightmost.right=null, and set cur=cur.right;

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> inorderTraversal(TreeNode root) {  
     List<Integer> res=new ArrayList<Integer>();  
     if(root==null) return res;  
     while(root!=null){  
       if(root.left==null){  
         res.add(root.val);  
         root=root.right;  
       }  
       else{  
         TreeNode pre=root.left;  
         while(pre.right!=null && pre.right!=root) pre=pre.right;  
         if(pre.right==null){  
           pre.right=root;  
           root=root.left;  
         }  
         else{  
           res.add(root.val);  
           pre.right=null;  
           root=root.right;  
         }  
       }  
     }  
     return res;  
   }