94. 二叉树的中序遍历

---

题目

描述： 给定一个二叉树的根节点 root，返回它的中序遍历结果（左子树 → 根节点 → 右子树）。

示例： 示例 1:

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

示例 2:

输入: root = []
输出: []

示例 3:

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

---

解题思路

核心方法

1. 递归法：利用中序遍历的定义，递归访问左子树，再访问根节点，最后递归访问右子树，思路直观，代码简洁。
2. 迭代法：使用栈模拟递归过程，手动控制节点的入栈和出栈顺序，避免递归的栈溢出风险，适合处理大规模树结构。

算法步骤（递归法）

1. 终止条件：当前节点为 null 时，直接返回。
2. 递归左子树：先递归遍历当前节点的左子树。
3. 访问根节点：将当前节点的值加入结果列表。
4. 递归右子树：再递归遍历当前节点的右子树。

---

代码实现

递归法（Java）

import java.util.*;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class Solution {
    List<Integer> ans = new ArrayList<>();
    
    public List<Integer> inorderTraversal(TreeNode root) {
        inorder(root);
        return ans;
    }
    
    private void inorder(TreeNode root) {
        if (root == null) return;
        inorder(root.left);   // 遍历左子树
        ans.add(root.val);    // 访问根节点
        inorder(root.right);  // 遍历右子树
    }
}

迭代法（Java）

import java.util.*;

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        Deque<TreeNode> stack = new LinkedList<>();
        
        TreeNode curr = root;
        while (curr != null || !stack.isEmpty()) {
            // 先遍历到最左子节点
            while (curr != null) {
                stack.push(curr);
                curr = curr.left;
            }
            // 弹出栈顶节点（当前最左节点）
            curr = stack.pop();
            ans.add(curr.val);
            // 转向右子树
            curr = curr.right;
        }
        return ans;
    }
}

---

复杂度分析

递归法

• 时间复杂度：O(n)，其中 n 是二叉树的节点数。每个节点会被访问一次。
• 空间复杂度：O(h)，h 是二叉树的高度。递归栈的深度取决于树的高度，最坏情况下（链状树）为 O(n)。

迭代法

• 时间复杂度：O(n)，每个节点入栈和出栈各一次。
• 空间复杂度：O(h)，栈的大小取决于树的高度，最坏情况下为 O(n)。

---

总结

1. 递归法是中序遍历最直观的实现方式，代码简洁易读，但对于深度极大的树可能出现栈溢出。
2. 迭代法通过手动维护栈来模拟递归过程，空间和时间效率与递归法一致，且避免了栈溢出问题。
3. 中序遍历在二叉搜索树（BST）中尤为重要，因为其遍历结果是升序序列，可用于验证BST的合法性。

---