Given a binary tree, return the inorder traversal of its nodes' values.
For example:
Given binary tree [1,null,2,3],

   1
    \
     2
    /
   3
return [1,3,2].

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

歸于In-order Traversal, stack & recursive總結(jié)Link：http://www.itdecent.cn/p/4728e9023ac7

Solution1：Recursion

思路： Regular Recursion for In-order traversal
Time Complexity: O(N) Space Complexity: O(N) 遞歸緩存

Solution2：Stack

思路： Regular Stack for In-order traversal
Time Complexity: O(N) Space Complexity: O(N)

Solution3：Morris Traversal

思路： Instead of 用stack或遞歸 回到父結(jié)點parent，找到parent在左樹中In-order遍歷時的前驅(qū)結(jié)點c，將c.right=parent。這樣都創(chuàng)建好return link好后，遍歷時只需要能左就左，左沒有就右即可。創(chuàng)建return link 是在第一次訪問被return node做的，如剛開始時第一次到root，做好左樹"右下"root的In-order前驅(qū).right=root，做好這個link后向左樹繼續(xù)訪問，（重復(fù)此過程）這樣之后訪問到當(dāng)時"root的前驅(qū)"就可以通過.right 回到root，回到root的時候?qū)⒅貜?fù)此創(chuàng)建return link過程將return link去掉恢復(fù)成原來樣子。
這樣一來空間復(fù)雜度就是O(1) ，時間復(fù)雜度雖然多了找parent在左樹前驅(qū)的過程，A n-node binary tree has n-1 edges，但每個edge最多還是3次(1次建立return link時，1次遍歷時，1次恢復(fù)時)所以還是O(N)。
Time Complexity: O(N) Space Complexity: O(1)

Solution1 Code：

class Solution1 {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if(root == null) return result;
        
        // method: recursion
        helper(root, result);
        return result;
    }

    private void helper(TreeNode root, List<Integer> result) {
        if (root.left != null) {
            helper(root.left, result);
        }
        result.add(root.val);
        if (root.right != null) {
            helper(root.right, result);
        }
    }
}

Solution2 Code：

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if(root == null) return list;
        Deque<TreeNode> stack = new ArrayDeque<>();
        while(root != null || !stack.isEmpty()){
            while(root != null){
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            list.add(root.val);
            root = root.right;
        }
        return list;
    }
}

Solution3 Code：

class Solution3 {
    public List<Integer> inorderTraversal(TreeNode root) {
        if(root == null) return new ArrayList<Integer>();
        List<Integer> res = new ArrayList<Integer>();
        
        TreeNode pre = null;
        while(root != null){
            if(root.left == null){
                // no need to make (root's precursor in in-order).right = root to return since there is no left
                res.add(root.val);
                root = root.right;
            }else{
                // need to make (root's precursor in in-order).right = root to return
                // find (root's precursor in in-order)
                pre = root.left;
                while(pre.right != null && pre.right != root){
                    pre = pre.right;
                }
                if(pre.right == null){
                    // (root's precursor in in-order).right = root to return 
                    pre.right = root;
                    root = root.left;
                }else{
                    // if already Morris-linked, remove it to make it restored
                    pre.right = null;
                    res.add(root.val);
                    root = root.right;
                }
            }
        }
        return res;
    }
}