• 中文 • Walking in Code

二叉树中序遍历 - 递归、迭代与 Morris 解法完全指南

通过交互式可视化掌握二叉树中序遍历。学习递归、迭代（栈）和 Morris O(1) 空间解法。用完整的 Java、Python、JavaScript 模板解决 LeetCode 94。

#algorithm #binary-tree #tree-traversal #inorder #visualization #interview #morris-traversal #bst

简介

中序遍历遵循左 → 根 → 右的模式：

  1. 遍历左子树
  2. 访问当前节点
  3. 遍历右子树

BST 的魔法 ✨

对于二叉搜索树（BST），中序遍历按升序排列访问节点！这是中序遍历最重要的特性。

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

中序遍历: 1 → 2 → 3 → 4 → 5 → 6 → 7  (有序！)

为什么面试官喜欢考它

  • 对 BST 问题至关重要（第 k 小、验证 BST 等）
  • 测试对递归和栈操作的理解
  • Morris 遍历展示空间优化的掌握程度
  • 是许多高级树算法的基础

何时使用中序遍历

  • BST 中第 k 小/大元素（LC 230）
  • 验证 BST（LC 98）
  • 将 BST 转换为有序列表
  • 查找 BST 的 floor/ceiling
  • 恢复 BST（LC 99）

直观理解

        1
       / \
      2   3
     / \
    4   5

中序遍历: 4 → 2 → 5 → 1 → 3
         (左→根→右)

访问顺序:
  步骤 1: 向左到 2，再向左到 4
  步骤 2: 访问 4（无子节点）
  步骤 3: 回溯，访问 2
  步骤 4: 向右，访问 5
  步骤 5: 回溯到 1，访问 1
  步骤 6: 向右，访问 3

交互式可视化

观察算法逐步遍历树的过程。比较递归、迭代和 Morris 方法！

Inorder (Left→Root→Right) - Iterative
1245367
Step 1 / 0INIT

Ready to start

Stack
Empty
Result
[]
Current
Visited
In Stack

解法一：递归方法

最直观的解法：向左走，访问，向右走。

代码模板

Loading...

工作原理

  1. 基本情况：如果节点为空，返回
  2. 递归左子树：先处理整个左子树
  3. 访问根节点：添加当前节点的值
  4. 递归右子树：然后处理右子树

调用栈自动处理”向上返回”的逻辑。

解法二：迭代方法（栈）

关键洞察：我们需要在访问任何节点之前尽可能向左走。

代码模板

Loading...

逐步演示

树结构:       1
             / \
            2   3
           /
          4

步骤 1: 压入 1, 向左          栈: [1]
步骤 2: 压入 2, 向左          栈: [1, 2]
步骤 3: 压入 4, 向左          栈: [1, 2, 4]
步骤 4: 无左子节点, 弹出 4, 访问   结果: [4]
步骤 5: 无右子节点, 弹出 2, 访问   结果: [4, 2]
步骤 6: 向右(无), 弹出 1, 访问    结果: [4, 2, 1]
步骤 7: 向右到 3
步骤 8: 压入 3, 无左, 弹出 3, 访问 结果: [4, 2, 1, 3]

最终结果: [4, 2, 1, 3]

模式总结

while (current 存在 OR 栈非空):
    1. 一直向左走（压入所有左节点）
    2. 弹出并访问
    3. 向右走（成为新的 current）

解法三：Morris 遍历（O(1) 空间）

Morris 遍历使用线索来消除栈。它临时创建从前驱节点回到后继节点的链接。

与前序遍历的关键区别

  • 前序 Morris：创建线索之前访问
  • 中序 Morris：通过线索返回之后访问

代码模板

Loading...

线索工作原理

原始树:                  添加线索后:
      4                     4
     / \                   / \
    2   6                 2   6
   / \                   / \
  1   3                 1   3
                             \
                              → (线索指向 4)

线索: 3 的右指针指向 4（其中序后继）

访问时机

对于中序遍历，我们在以下情况访问：
1. 无左子节点 → 访问，向右移动
2. 线索存在（返回时） → 访问，删除线索，向右移动

不是在创建线索时访问！那是前序遍历。

LeetCode 94：二叉树的中序遍历 (LC 94)

经典的中序遍历问题。三种解法都可以直接使用。

示例：

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

输出: [1, 3, 2]

问题二：BST 中第 K 小的元素 (LC 230)

由于中序遍历对 BST 给出有序序列，只需返回第 k 个元素！

public int kthSmallest(TreeNode root, int k) {
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode current = root;
    
    while (current != null || !stack.isEmpty()) {
        while (current != null) {
            stack.push(current);
            current = current.left;
        }
        
        current = stack.pop();
        if (--k == 0) return current.val;  // 找到第 k 个！
        
        current = current.right;
    }
    
    return -1;  // k > 树的大小
}

问题三：验证二叉搜索树 (LC 98)

使用中序遍历并检查每个值是否大于前一个值：

def isValidBST(root: Optional[TreeNode]) -> bool:
    stack = []
    current = root
    prev = float('-inf')
    
    while current or stack:
        while current:
            stack.append(current)
            current = current.left
        
        current = stack.pop()
        if current.val <= prev:  # 必须严格递增
            return False
        prev = current.val
        
        current = current.right
    
    return True

复杂度分析

方法时间空间说明
递归O(n)O(h)h = 树高，最坏 O(n)
迭代O(n)O(h)显式栈
MorrisO(n)O(1)每条边最多访问两次

空间对比

       平衡树               斜树
           O                   O
          / \                   \
         O   O                   O
        / \ / \                   \
       O  O O  O                   O

栈深度: O(log n)           栈深度: O(n)

常见错误

1. 迭代：忘记外层条件

// 错误：只检查栈
while (!stack.isEmpty()) {  // 漏掉了初始的 current
    // ...
}

// 正确：两者都检查
while (current != null || !stack.isEmpty()) {
    // ...
}

2. Morris：访问时机错误

# 中序遍历错误：向左走之前访问
if not predecessor.right:
    result.append(current.val)  # 太早了！
    predecessor.right = current
    current = current.left

# 正确：返回时访问
if predecessor.right:  # 线索存在
    predecessor.right = None
    result.append(current.val)  # 现在访问！
    current = current.right

3. 没有处理空树

// 总是先检查空根节点
function inorderTraversal(root) {
  if (!root) return [];  // 别忘了！
  // ...
}

边界情况

  1. 空树：返回 []
  2. 单节点：返回 [root.val]
  3. 左斜树：测试最大栈深度
  4. 右斜树：测试迭代逻辑
  5. 完全二叉树：标准平衡情况

面试技巧

如何解释中序遍历

  1. “中序意味着 左 → 根 → 右”
  2. “对于 BST，这给出有序序列”
  3. “栈模拟递归中的调用栈”
  4. “Morris 创建临时线索来节省空间”

后续问题

问题答案
”为什么对 BST 使用中序？“给出升序排列
”如何获得降序？“右 → 根 → 左（反向中序）
“可以用 O(1) 空间吗？“是的，Morris 遍历
”如果不能修改树呢？“使用栈，O(h) 空间

与其他遍历的比较

属性前序中序后序
顺序根→左→右左→根→右左→右→根
BST 有序？否是 ✓否
用例复制树BST 操作删除树
访问时机子节点之前子节点之间子节点之后

总结

方面递归迭代Morris
简单程度⭐⭐⭐⭐⭐⭐
空间O(h)O(h)O(1)
修改树否否是（临时）
最适合学习面试优化

需要记住的关键模式：

  1. 中序 = 左 → 根 → 右
  2. BST + 中序 = 有序序列
  3. 迭代：一直向左压栈，弹出并访问，向右走
  4. Morris：线索存在时访问（不是创建时）

中序遍历对 BST 问题至关重要。掌握这三种实现方法！

← 返回博客列表