94. 二叉树的中序遍历#

生活中的遍历启示#

想象你在一个迷人的森林里散步。森林里的每棵树都有自己独特的故事，而你的任务是以一种特定的方式依次聆听每棵树的声音。中序遍历就像是这样一次有序的森林漫步：先听左侧的树木，然后是当前所在的树，最后是右侧的树木。

问题描述#

题目目标#

给定一个二叉树的根节点 root ，返回它的中序遍历结果。中序遍历的访问顺序为：左子树、根节点、右子树。

示例 1#

输入： root = [1,null,2,3] 输出： [1,3,2] 二叉树示意：

text

说明： 按“左子树 -> 根节点 -> 右子树”的顺序访问，遍历结果正好是 [1,3,2]。

补充说明#

二叉树通常使用层序数组表示，null 表示该位置没有节点。

遍历的本质#

二叉树的中序遍历（LeetCode第94题）遵循一个优雅的顺序：

先访问左子树
再访问根节点
最后访问右子树

这种方式特别适合有序二叉搜索树，因为它会按照升序输出节点值。

思路的进化之路#

第一站：递归的诗意#

递归是解决树遍历最自然的方式。就像讲一个故事：要了解整个故事，你需要先了解故事的左半部分，然后是核心情节，最后是右半部分。

public List<Integer> inorderTraversal(TreeNode root) {
    // 用于保存最终的中序遍历结果（按左->中->右顺序）
    List<Integer> result = new ArrayList<>();
    // 从根节点开始递归遍历整棵树
    traverse(root, result);
    // 返回收集好的遍历结果
    return result;
}

private void traverse(TreeNode node, List<Integer> result) {
    // 递归终止条件：当前节点为空，说明这条分支已经走到底
    if (node == null) return;

    // 1）先递归遍历左子树，保证左侧节点先被访问
    traverse(node.left, result);

    // 2）访问当前节点，把节点值加入结果列表
    result.add(node.val);

    // 3）最后递归遍历右子树
    traverse(node.right, result);
}

java

第二站：迭代的智慧#

递归虽然优雅，但对于深度较大的树可能导致栈溢出。迭代提供了一种显式管理”故事进度”的方式。

public List<Integer> inorderTraversal(TreeNode root) {
    // 保存最终中序遍历结果
    List<Integer> result = new ArrayList<>();
    // 显式栈：模拟递归调用栈，用于回溯父节点
    Deque<TreeNode> stack = new LinkedList<>();
    // 当前正在访问的节点指针，初始指向根节点
    TreeNode current = root;

    // 只要“还有当前节点可向左深入”或“栈中还有待处理节点”就继续
    while (current != null || !stack.isEmpty()) {
        // 1）不断向左走，把沿途节点全部入栈
        while (current != null) {
            // 入栈后，后续会回到这个节点处理它和它的右子树
            stack.push(current);
            // 继续向左子节点深入
            current = current.left;
        }

        // 2）左侧走到尽头后，弹出栈顶节点（即当前子树最左未处理节点）
        current = stack.pop();
        // 访问该节点并记录其值
        result.add(current.val);

        // 3）转向该节点的右子树，重复“先左后中再右”的过程
        current = current.right;
    }

    // 返回中序遍历结果
    return result;
}

java

遍历的艺术与算法#

模式匹配#

让我们通过具体的树来理解遍历过程：

     4
   /   \
  2     6
 / \   / \
1   3 5   7

plaintext

递归遍历顺序： 1 → 2 → 3 → 4 → 5 → 6 → 7

迭代遍历步骤：

压入1、2
弹出2，访问，压入3
弹出3
弹出4，访问
压入5、6 … 如此类推

复杂度分析#

递归方法：

时间复杂度：O(n)，每个节点访问一次
空间复杂度：O(h)，h为树的高度（递归栈）
优点：代码简洁，易于理解
缺点：可能栈溢出

迭代方法：

时间复杂度：O(n)
空间复杂度：O(h)
优点：显式控制遍历，避免递归栈溢出
缺点：代码略显复杂

进阶思考#

Morris遍历：O(1)空间复杂度的遍历方法
如何处理平衡与非平衡二叉树？
前序、中序、后序遍历的本质区别？

实际应用场景#

二叉搜索树的排序
表达式求值
文件系统遍历
编译器语法树分析

小结#

中序遍历教会我们：

递归思想的优雅
如何系统地遍历树形结构
迭代与递归的权衡
数据结构遍历的通用思维方式

记住：遍历树就像漫步在知识的森林，重要的是保持好奇和系统性！