94. 二叉树的中序遍历

给定一个二叉树的根节点 root ，返回它的 中序 遍历。

示例 1：

输入：root = [1,null,2,3]
输出：[1,3,2]

示例 2：

输入：root = []
输出：[]

示例 3：

输入：root = [1]
输出：[1]

示例 4：

输入：root = [1,2]
输出：[2,1]

示例 5：

输入：root = [1,null,2]
输出：[1,2]

提示：

• 树中节点数目在范围 [0, 100] 内
• -100 <= Node.val <= 100

进阶: 递归算法很简单，你可以通过迭代算法完成吗？

解法

中序遍历顺序为左->中->右。

整体流程如下：

1. 先一直遍历最左边的线路，直到节点为空。
2. 弹出当前节点。此时该节点左子树为空，判断其右子树是否为空。
3. 右子树若为空则弹出父节点，重复步骤2。
4. 右子树不为空则对右子树重复步骤1。

第1步和第4步的条件都是节点不为空，第2步和第3步均在节点为空的条件下进行。

1. 递归

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        inOrder(root, list);
        return list;
    }

    public void inOrder(TreeNode root, List<Integer> list){
         if(root == null){
            return;
        }

        inOrder(root.left, list);
        list.add(root.val);
        inOrder(root.right, list);
    }
}

2. 迭代

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

        Stack<TreeNode> stack = new Stack<>();
        
        while(!stack.isEmpty() || root != null){
            if (root != null){
                //当前节点不为空，一直向左子节点移动
                stack.push(root);
                root = root.left;
            } else {
                //当前节点为空，弹出栈顶元素，并向其右子节点移动
                root = stack.pop();
            	list.add(root.val);
            	root = root.right;
            } 
        }
        return list;
    }
}