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?

题意：中序遍历一个二叉树，以数组形式返回遍历结果。

思路：中序遍历就是按照左中右的顺序遍历数组，因此我们可以先遍历根节点的左子树，然后遍历根节点，最后遍历根节点的右子树。如果左子树或者右子树仍然是非叶子几点，我们可以用上面的方法递归对左右子树进行调用。直到遍历到的节点是一个叶子节点，我们将它加入到list中。

public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    if (root == null) {
        return res;
    }
    
    dfs(root, res);
    
    return res;
}

public void dfs(TreeNode root, List<Integer> res) {
    if (root.left == null && root.right == null) {
        res.add(root.val);
        return;
    }
    
    if (root.left != null) {
        dfs(root.left, res);
    }
    res.add(root.val);
    if (root.right != null) {
        dfs(root.right, res);
    }
    
}

题目最后要求不用递归的解法。因为是中序遍历，输出完左子树后还要再输出自己的根节点，所以我们需要一个数据结构能够记得之前遍历过的根节点，由此想到了用栈。
第一步是要找到最左节点，就从根节点开始不停向左找下去，如果自己还有左节点，就把自己加入到栈中
第二步，弹出当前栈顶，这就是最左节点了
第三步，如果当前弹出元素还有右节点，那么证明此节点有右子树，需要把右节点加到栈中，然后对这个右子树进行中序遍历；如果没有右节点，则需要遍历到自己的父节点了。

public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> list = new ArrayList<Integer>();

    Stack<TreeNode> stack = new Stack<TreeNode>();
    TreeNode cur = root;

    while(cur!=null || !stack.empty()){
        while(cur!=null){
            stack.add(cur);
            cur = cur.left;
        }
        cur = stack.pop();
        list.add(cur.val);
        cur = cur.right;
    }

    return list;
}