144. Binary Tree Preorder Traversal Leetcode Java

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

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

   1
    \
     2
    /
   3

return [1,2,3].

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

Solution:

I will present 3 solutions.
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> preorderTraversal(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;  
     res.add(root.val);  
     helper(root.left,res);  
     helper(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. The difference between this one with inorder tranversal is the timing of adding the root.val to result list. 

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

3rd, Iteration with no extra space: Morris Preorder 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 preorder 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;
The difference between this with inorder traversal is that the timing of adding the root.
For inorder traversal, we add the root.val when we back to root from root.left, but for pre-order traversal, we add root.val when we first visit the root.node and then traversal the root.left, so when we index back to root, we directly jump to root.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> preorderTraversal(TreeNode root) {  
     List<Integer> res=new ArrayList<Integer>();  
     if(root==null) return res;  
     while(root!=null){  
       if(root.left!=null) {  
         TreeNode pre=root.left;  
         while(pre.right!=null && pre.right!=root){  
           if(pre.right!=null) pre=pre.right;  
           else pre=pre.left;  
         }  
         if(pre.right==root){  
           pre.right=null;  
           root=root.right;  
         }  
         else{  
           pre.right=root;  
           res.add(root.val);  
           root=root.left;  
         }  
       }  
       else{  
         res.add(root.val);  
         root=root.right;  
       }  
     }  
     return res;  
   }