LeetCode:Binary Tree Inorder Traversal

Binary Tree Inorder Traversal

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 1: Use a stack. Time:O(n) and space O(logn). 

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

public  ArrayList<Integer> inorderTraversal(TreeNode root) {
            // Start typing your Java solution below
            // DO NOT write main() function
            ArrayList<Integer> res = new ArrayList<Integer>();
            if(root==null) return res;
            
            Stack<TreeNode> s = new Stack<TreeNode>();
            TreeNode cur = root;
            while(!s.isEmpty()||cur!=null){
                if(cur!=null){
                    s.push(cur); 
                    cur=cur.left;
                }else{
                    cur=s.pop();
                    res.add(cur.val);
                    cur=cur.right;
                }
            }
            return res;
        }

Solution 2: Morris algorithm. Time: O(nlogn) but space O(1). 

public class Solution {
    public ArrayList<Integer> inorderTraversal(TreeNode root) {
        // Start typing your Java solution below
        // DO NOT write main() function
        ArrayList<Integer> res = new ArrayList<Integer>();
        TreeNode cur=root,next=null;
        while(cur!=null){
            if(cur.left!=null){
                next=cur;
                cur=cur.left;
            
                TreeNode temp=cur;
                while(temp.right!=null && temp.right!=next){
                    temp=temp.right;
                }    
            
                if(temp.right==null){
                    temp.right=next;
                }else{
                    temp.right=null;
                    res.add(next.val);
                    cur=next.right;
                }
            }else{
                res.add(cur.val);
                cur=cur.right;
            }
        }
        return res;
    }
}

PostOrder NonRecursive Traversal：

public static ArrayList<Integer> postOrderNonRecursive(TreeNode root){
         ArrayList<Integer> res = new ArrayList<Integer>();
         if(root==null) return res;
         
         Stack<TreeNode> s = new Stack<TreeNode>();
         TreeNode cur = root;
         
         while(true){
             if(cur.right!=null)
                 s.push(cur.right);
             s.push(cur);
             if(cur.left!=null)
                 cur=cur.left;
             else{
                 cur = s.pop();
                 while(!s.isEmpty() && (cur.right==null || cur.right!=s.peek())){
                     res.add(cur.val);
                     cur=s.pop();
                 }
                 if(cur.right!=null && !s.isEmpty()){
                     s.pop();
                     s.push(cur);
                     cur=cur.right;
                 }
                 if(s.isEmpty()){
                     res.add(cur.val);
                     break;
                 }
             }
         }
         return res;
     }