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总结Link：http://www.jianshu.com/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或递归 回到父结点parent，找到parent在左树中In-order遍历时的前驱结点c，将c.right=parent。这样都创建好return link好后，遍历时只需要能左就左，左没有就右即可。创建return link 是在第一次访问被return node做的，如刚开始时第一次到root，做好左树"右下"root的In-order前驱.right=root，做好这个link后向左树继续访问，（重复此过程）这样之后访问到当时"root的前驱"就可以通过.right 回到root，回到root的时候将重复此创建return link过程将return link去掉恢复成原来样子。
这样一来空间复杂度就是O(1) ，时间复杂度虽然多了找parent在左树前驱的过程，A n-node binary tree has n-1 edges，但每个edge最多还是3次(1次建立return link时，1次遍历时，1次恢复时)所以还是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;
    }
}