• 中文 • Walking in Code

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

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

#algorithm #binary-tree #tree-traversal #preorder #visualization #interview #morris-traversal

简介

前序遍历是三种基本的深度优先树遍历方法之一。遍历顺序遵循根 → 左 → 右，即：

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

为什么面试官喜欢考它

前序遍历是常见的面试题，因为：

  • 测试对递归与迭代权衡的理解
  • 是许多树问题的基础（序列化、克隆、路径查找）
  • Morris 遍历测试对树操作的高级理解
  • 简单到可以快速编码，复杂到可以讨论权衡

何时使用前序遍历

  • 树的序列化/反序列化（LC 297）
  • 创建树的副本
  • 从表达式树获取前缀表达式
  • 检查子树（LC 572）

直观理解

        1
       / \
      2   3
     / \
    4   5

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

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

交互式可视化

探索三种遍历方法。观察算法逐步遍历树的过程！

Preorder (Root→Left→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

栈操作:
1. 压入 1           栈: [1]
2. 弹出 1, 访问     结果: [1], 压入 3, 压入 2 → 栈: [3, 2]
3. 弹出 2, 访问     结果: [1,2], 栈: [3]
4. 弹出 3, 访问     结果: [1,2,3], 栈: []

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

为什么先压入右子节点？

栈是后进先出（LIFO）的。我们想先处理左子节点：

  • 压入右子节点 → 它在栈底
  • 压入左子节点 → 它在栈顶
  • 弹出时先得到左子节点 ✓

写法二：使用 cur 指针（统一模板）

这种写法使用 cur 指针来控制遍历方向，可以与中序、后序遍历保持统一的代码结构。

Loading...

核心思想：

  1. cur 指针：追踪当前遍历位置
  2. 一路向左：沿途立即访问每个节点（前序特点）
  3. 栈保存节点：用于稍后访问右子树
  4. 转向右边：左边走完后，转向右子树

为什么需要 cur 指针？

使用 cur 指针的好处是可以和中序、后序遍历形成统一模板：

  • 前序：进入节点时访问（往左走时）
  • 中序：离开节点时访问（从栈弹出时）
  • 后序：左右都处理完时访问

这种写法更利于记忆和理解遍历算法的本质。

两种写法对比

特点写法一（直接出栈）写法二（cur 指针）
代码行数更少略多
理解难度简单直观需理解指针移动
统一性前序独特三种遍历统一
推荐场景只写前序需要记忆三种遍历

建议：如果只做前序遍历，用写法一更简洁；如果想掌握统一模板，用写法二更有利于理解和记忆。

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

Morris 遍历通过使用线索二叉树临时修改树结构来实现 O(1) 空间。

核心思想

不使用栈，而是创建从节点回到其祖先节点的临时链接（线索）。这使我们能够在不使用额外空间的情况下返回父节点。

代码模板

Loading...

Morris 前序遍历 vs 中序遍历

关键区别：何时访问节点。

  • 前序 Morris：创建线索之前访问节点，然后向左移动
  • 中序 Morris：通过线索返回之后访问节点
前序访问时机:
1. 无左子节点？ → 访问，向右移动
2. 有左子节点，无线索？ → 访问，创建线索，向左移动
3. 有左子节点，有线索？ → 删除线索，向右移动

关键：向左之前先访问！

线索可视化

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

统一模板：三种遍历的代码结构

使用 cur 指针，可以让前序、中序、后序遍历保持统一的代码结构，只需改变访问节点的时机。

核心模板

所有三种遍历都遵循相同的框架：

TreeNode cur = root;
Deque<TreeNode> stack = new ArrayDeque<>();

while (cur != null || !stack.isEmpty()) {
    // 阶段1：向左探索
    while (cur != null) {
        // 前序：在这里访问节点 ⭐
        stack.push(cur);
        cur = cur.left;
    }
    
    // 阶段2：处理栈顶
    cur = stack.pop();
    // 中序：在这里访问节点 ⭐
    
    // 阶段3：转向右子树
    cur = cur.right;
}

三种遍历对比

前序遍历（根-左-右）

while (cur != null || !stack.isEmpty()) {
    while (cur != null) {
        result.add(cur.val);  // ⭐ 进入时访问
        stack.push(cur);
        cur = cur.left;
    }
    cur = stack.pop();
    cur = cur.right;
}

中序遍历（左-根-右）

while (cur != null || !stack.isEmpty()) {
    while (cur != null) {
        stack.push(cur);
        cur = cur.left;
    }
    cur = stack.pop();
    result.add(cur.val);     // ⭐ 弹出时访问
    cur = cur.right;
}

后序遍历（左-右-根）

TreeNode prev = null;
while (cur != null || !stack.isEmpty()) {
    while (cur != null) {
        stack.push(cur);
        cur = cur.left;
    }
    cur = stack.peek();
    
    if (cur.right == null || cur.right == prev) {
        result.add(cur.val);  // ⭐ 左右都处理完才访问
        stack.pop();
        prev = cur;
        cur = null;
    } else {
        cur = cur.right;
    }
}

统一模板对比表

特征前序中序后序
访问时机往左走时从栈弹出时左右都处理完
初始化cur = rootcur = rootcur = root; prev = null
向左探索push + 访问 + leftpush + leftpush + left
栈操作poppoppeek
右子树处理直接转向直接转向条件转向
额外变量无无prev（标记已访问）

记忆技巧

前序 = 先访问：进入节点时就访问，然后继续向左

  • 就像见到新朋友先打招呼，再深入交流

中序 = 中间访问：左边处理完，访问自己，再去右边

  • 就像吃汉堡：左面包 → 肉（重点）→ 右面包

后序 = 后访问：等孩子们都处理完，最后才访问自己

  • 就像家长：先照顾好孩子，最后才考虑自己

为什么前序不需要 cur？

前序遍历其实不必使用 cur 指针，因为访问顺序和 DFS 探索顺序一致：

// 前序简洁写法（写法一）
stack.push(root);
while (!stack.isEmpty()) {
    TreeNode node = stack.pop();
    result.add(node.val);        // 出栈立即访问
    if (node.right != null) stack.push(node.right);
    if (node.left != null) stack.push(node.left);
}

但使用 cur 指针（写法二）的好处是：

  1. 统一思维模型：三种遍历用同一套框架
  2. 便于记忆：只需记住访问时机的区别
  3. 易于理解：清楚地看到”探索”和”访问”的分离

实战建议

面试场景：

  • 只做前序：用简洁写法（写法一），代码更短
  • 做多种遍历：用统一模板（写法二），展示深度理解

学习建议：

  1. 先掌握每种遍历的独立实现
  2. 再学习统一模板，理解本质
  3. 根据场景选择合适的写法

LeetCode 144：二叉树的前序遍历 (LC 144)

这是前序遍历的经典问题。上述三种解法都可以直接解决。

示例：

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

输出: [1, 2, 3]

复杂度分析

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

为什么 Morris 是 O(n) 时间？

虽然有嵌套循环，但每条边最多被遍历两次：

  1. 创建线索时一次
  2. 删除线索时一次

总计：2 × (n-1) 条边 = O(n)

常见错误

1. 压栈顺序错误（迭代）

// 错误：先压左子节点，最后才处理
if (node.left != null) stack.push(node.left);
if (node.right != null) stack.push(node.right);

// 正确：先压右子节点，再压左子节点
if (node.right != null) stack.push(node.right);
if (node.left != null) stack.push(node.left);

2. Morris：访问时机错误

# 前序遍历错误：在线索存在时访问
if predecessor.right:
    result.append(current.val)  # 太晚了！
    
# 正确：创建线索之前访问
if not predecessor.right:
    result.append(current.val)  # 现在访问！
    predecessor.right = current

3. 忘记边界条件

// 别忘了空值检查！
function preorder(root) {
  if (!root) return [];  // 必须的！
  // ...
}

边界情况

  1. 空树：返回 []
  2. 单节点：返回 [root.val]
  3. 左斜树：1→2→3→4（测试栈深度）
  4. 右斜树：同左斜树
  5. 完全二叉树：标准情况

面试技巧

如何解释

  1. 从递归开始（最容易理解）
  2. 解释为什么栈可以模拟递归
  3. 提及 Morris 作为 O(1) 空间优化
  4. 讨论权衡（Morris 临时修改树）

后续问题

  • “能用迭代实现吗？” → 栈解法
  • “能用 O(1) 空间吗？” → Morris 遍历
  • “如果不能修改树呢？” → 栈是最佳选择
  • “如何处理非常深的树？” → Morris 防止栈溢出

何时不使用前序遍历

  • 从 BST 获取有序序列：使用中序（得到升序）
  • 自底向上删除树：使用后序
  • 层序遍历：使用 BFS 和队列

总结

方面递归迭代Morris
简单程度⭐⭐⭐⭐⭐⭐
空间O(h)O(h)O(1)
修改树否否是（临时）
面试使用热身标准加分项

需要记住的关键模式：

  1. 前序 = 根 → 左 → 右
  2. 迭代：先压右，再压左（LIFO）
  3. Morris：向左之前先访问
  4. 所有方法时间复杂度都是 O(n)

掌握这三种方法，你就能自信地应对任何树遍历问题！

← 返回博客列表