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

简介

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

1. 遍历左子树
2. 遍历右子树
3. 访问当前节点（最后！）

为什么先处理子节点？

后序遍历在以下场景至关重要：

• 先处理子节点再处理父节点（自底向上计算）
• 安全删除树节点（先删除子节点再删除父节点）
• 计算子树属性（高度、大小、和）

何时使用后序遍历

• 删除树（先释放子节点再释放父节点）
• 表达式树求值（先处理操作数再处理运算符）
• 计算树的高度/深度
• 序列化树以便重建
• 依赖解析（先处理依赖项）

直观理解

        1
       / \
      2   3
     / \
    4   5

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

访问顺序:
  步骤 1: 向左到 2，再向左到 4
  步骤 2: 访问 4（无子节点）
  步骤 3: 回溯，向右到 5，访问 5
  步骤 4: 回溯，访问 2（两个子节点都处理完了）
  步骤 5: 回溯到 1，向右，访问 3
  步骤 6: 回溯，访问 1（根节点最后！）

关键洞察

在后序遍历中，一个节点在其所有后代之后被访问。这就是为什么：

• 根节点 1 最后被访问
• 每个父节点都在其子节点之后被访问

交互式可视化

逐步观察后序遍历。注意父节点如何等待子节点处理完成！

Method:RecursiveIterativeMorris

Speed:0.5x1x2x4x

Postorder (Left→Right→Root) - Iterative

Step 1 / 0INIT

Ready to start

Stack

Empty

Result

[]

Current

Visited

In Stack

⟲ Reset← Prev▶ PlayNext →

解法一：递归方法

最简洁的解法：递归左子树，递归右子树，然后访问。

代码模板

JavaPythonJavaScript

Loading...

工作原理

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

递归自然确保子节点在父节点之前被处理。

解法二：迭代方法

后序遍历是迭代实现中最棘手的。有两种常见方法：

方法 A：反转前序技巧

洞察：后序（左→右→根）是修改后的前序（根→右→左）的反转

修改后的前序: 根 → 右 → 左  = [1, 3, 2, 5, 4]
反转它:       左 → 右 → 根  = [4, 5, 2, 3, 1] ✓ 后序！

JavaPythonJavaScript

Loading...

方法 B：经典的 prev 指针法

跟踪上一个访问的节点来判断右子树是否处理完成：

JavaPythonJavaScript

Loading...

比较

方法	时间	空间	复杂度
反转前序	O(n)	O(n)	简单
prev 指针	O(n)	O(h)	较难

prev 指针方法使用更少的空间，但需要仔细处理。

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

Morris 后序遍历是三种遍历中最复杂的。它需要：

1. 一个虚拟节点作为根节点的父节点
2. 反转并收集右路径段

代码模板

JavaPythonJavaScript

Loading...

工作原理

带虚拟节点的树:
     dummy
      /
     1
    / \
   2   3

当发现从 3→dummy 的线索时（返回时）：
1. 从 1 到 3 的路径逆序收集

这很复杂！反转操作从 current.left 到 predecessor 
逆序收集节点。

为什么如此复杂？

后序遍历最后访问根节点，但 Morris 遍历在”向下”走时（通过线索）处理节点。我们需要：

1. 收集右子指针的路径
2. 反转它以获得后序
3. 再次反转以恢复树

建议：在面试中，除非明确要求 O(1) 空间，否则使用反转前序技巧。

LeetCode 145：二叉树的后序遍历 (LC 145)

经典的后序遍历问题。

示例：

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

输出: [3, 2, 1]

应用：安全删除树

后序遍历对于删除树节点至关重要：

// 安全删除树的所有节点
void deleteTree(TreeNode node) {
    if (node == null) return;
    
    deleteTree(node.left);   // 先删除左子树
    deleteTree(node.right);  // 删除右子树
    
    // 现在可以安全删除当前节点
    // （没有指向子节点的悬空指针）
    node.left = null;
    node.right = null;
    // node 现在可以安全地被垃圾回收
}

应用：计算树的高度

def treeHeight(root):
    if not root:
        return 0
    
    # 后序：先获取子节点的高度
    left_height = treeHeight(root.left)
    right_height = treeHeight(root.right)
    
    # 然后计算当前节点的高度
    return 1 + max(left_height, right_height)

复杂度分析

方法	时间	空间	说明
递归	O(n)	O(h)	调用栈深度 = 树高
迭代（反转）	O(n)	O(n)	结果以反转形式存储
迭代（prev）	O(n)	O(h)	栈大小 = 树高
Morris	O(n)	O(1)	实现最复杂

常见错误

1. 迭代：压栈顺序错误

// 对于反转前序技巧：
// 我们要 根→右→左，然后反转

// 先压左子节点（这样右子节点先处理 = 根→右→左）
if (node.left != null) stack.push(node.left);
if (node.right != null) stack.push(node.right);

2. prev 指针：忘记重置 current

# 错误：current 仍然指向弹出的节点
prev = stack.pop()
# 会尝试从已访问的节点向左走！

# 正确：将 current 设为 None
prev = stack.pop()
current = None  # 不要再向左走

3. 与其他遍历混淆

记住这些模式：
- 前序:  根 → 左 → 右  (最先访问)
- 中序:  左 → 根 → 右  (中间访问)
- 后序:  左 → 右 → 根  (最后访问)

边界情况

1. 空树：返回 []
2. 单节点：返回 [root.val]
3. 只有左子树：1→2→3 得到 [3, 2, 1]
4. 只有右子树：同样的模式
5. 完全二叉树：标准情况

面试技巧

如何解释后序遍历

1. “后序遍历在所有后代处理完后访问节点”
2. “顺序是 左 → 右 → 根”
3. “当你需要自底向上处理时很有用”
4. “迭代版本可以使用反转前序技巧”

选择哪种迭代方法？

情况	推荐
快速实现	反转前序
需要 O(h) 空间	prev 指针
要求 O(1) 空间	Morris（复杂！）
编程面试	反转前序（安全选择）

后续问题

• “能不用反转实现吗？” → prev 指针方法
• “O(1) 空间？” → Morris，但要说明复杂性
• “后序什么时候比前序好？” → 自底向上计算
• “实际应用场景？” → 删除树、依赖图

三种遍历的比较

树结构:     1
           / \
          2   3
         / \
        4   5

前序:  [1, 2, 4, 5, 3]  根在前
中序:  [4, 2, 5, 1, 3]  根在中间
后序:  [4, 5, 2, 3, 1]  根在后

属性	前序	中序	后序
根的位置	第一个	中间	最后
用例	克隆树	BST 有序	删除树
迭代难度	简单	中等	困难
Morris 难度	中等	中等	困难

总结

方面	递归	迭代	Morris
简单程度	⭐⭐⭐	⭐⭐	⭐
空间	O(h)	O(h) 或 O(n)	O(1)
面试选择	热身	首选	进阶

需要记住的关键模式：

1. 后序 = 左 → 右 → 根
2. 迭代技巧：根 → 右 → 左 的反转
3. 父节点在所有子节点之后访问
4. 非常适合自底向上的树操作

后序遍历是迭代实现中最棘手的遍历，但深入理解它展示了对树算法的掌握！