Problem

https://leetcode.com/problems/binary-tree-inorder-traversal/
Given a binary tree, return the inorder traversal of its nodes' values.

Example:

Input: [1,null,2,3]
   1
    \
     2
    /
   3

Output: [1,3,2]
Follow up: Recursive solution is trivial, could you do it iteratively?

Solutions:

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

// Solution 1: Recursive (mutable)
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
       // This is mutable. 在递归过程中这个数组在被更新
       List<Integer> result = new ArrayList<Integer>();
       inorderTraversalHelper(root, result);
       return result;
    }
   
    public void inorderTraversalHelper(TreeNode root, List<Integer> result) {
       if (root == null) {
           return;
       }
        
       inorderTraversalHelper(root.left, result);
       result.add(root.val);
       inorderTraversalHelper(root.right, result);        
    }
}

// Solution 2: Recursive (immutable) 
// 函数式编程思想
// 有额外的拷贝，需要使用额外的空间和时间
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) {
            return result;
        }

        List<Integer> l = inorderTraversal(root.left);
        List<Integer> r = inorderTraversal(root.right);
        
        result.addAll(l);
        result.add(root.val);
        result.addAll(r);
        
        return result;
    }
}

// Solution 3: Iterative
/*
use pushAllLeft() to push all the left children of one Node into the stack
1. Push all the left children of root into the stack until there's no more nodes.
2. Then pop from the stack which we'd call "current".
3. Add "current" to result list
4. Call pushAllLeft() on current's right child.
*/
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
      
        List<Integer> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        
        Stack<TreeNode> stack = new Stack<>();
        pushAllLeft(root, stack);
        
        while(!stack.empty()) {
            TreeNode current = stack.pop();
            result.add(current.val);
            pushAllLeft(current.right, stack);
        }
        
        return result;
    }
    
    // push all the left children of one Node into the stack
    public void pushAllLeft(TreeNode node, Stack<TreeNode> stack) {
        while(node != null) {
            stack.push(node);
            node = node.left;
        }
    }
}

Complexity：

1. 当这棵树是链表的情况（每个节点只有左子树）空间复杂度：Recusive 递归深度=O(n)，Iterative O(1)。
2. 当这棵树是满二叉树 空间复杂度: Recursive 递归深度=O(logn) , Iterative O(logn)

References:
https://www.youtube.com/watch?v=A6iCX_5xiU4
https://leetcode.com/problems/binary-tree-inorder-traversal/discuss/31213/Iterative-solution-in-Java-simple-and-readable