二叉树：递归思维的起点

第十章：二叉树 — 递归思维的起点

几乎所有的树结构面试题都可以用一句话概括：把大问题拆成左子树和右子树的小问题，然后合并结果。 这就是递归，而二叉树是练习递归思维最好的载体。

如果你能熟练写出二叉树的前序、中序、后序、层序遍历（递归和迭代两种），能解决最近公共祖先、序列化反序列化、路径和等经典题，你就掌握了递归的核心思想。后面的回溯、分治、动态规划，本质上都是这种"拆分 → 递归 → 合并"的模式。

Level 1 · 你需要知道的

10.1 二叉树的基本概念

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

关键性质：

• n 个节点的二叉树有 n-1 条边
• 高度为 h 的二叉树最多有 2^(h+1) - 1 个节点
• 完全二叉树的高度是 O(log n)

10.2 四种遍历

二叉树的遍历有四种，前三种是深度优先（DFS），最后一种是广度优先（BFS）：

# 前序遍历：根 → 左 → 右
def preorder(root):
    if not root:
        return []
    return [root.val] + preorder(root.left) + preorder(root.right)

# 中序遍历：左 → 根 → 右
def inorder(root):
    if not root:
        return []
    return inorder(root.left) + [root.val] + inorder(root.right)

# 后序遍历：左 → 右 → 根
def postorder(root):
    if not root:
        return []
    return postorder(root.left) + postorder(root.right) + [root.val]

# 层序遍历（BFS）
from collections import deque

def level_order(root):
    if not root:
        return []
    result = []
    queue = deque([root])
    while queue:
        level = []
        for _ in range(len(queue)):
            node = queue.popleft()
            level.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        result.append(level)
    return result

记忆法：前/中/后指的是根节点的访问位置。前序 = 根在前，中序 = 根在中，后序 = 根在后。左子树永远在右子树前面。

示例：对于这棵树：

        1
       / \
      2   3
     / \
    4   5

10.3 递归模板

二叉树的递归题几乎都遵循这个模板：

def solve(root):
    # 1. 基础情况（Base Case）
    if not root:
        return base_value

    # 2. 递归处理左右子树
    left_result = solve(root.left)
    right_result = solve(root.right)

    # 3. 合并结果
    return combine(root.val, left_result, right_result)

示例：求树的最大深度

def max_depth(root):
    if not root:
        return 0
    left = max_depth(root.left)
    right = max_depth(root.right)
    return max(left, right) + 1

示例：判断是否对称

def is_symmetric(root):
    def check(left, right):
        if not left and not right:
            return True
        if not left or not right:
            return False
        return (left.val == right.val and
                check(left.left, right.right) and
                check(left.right, right.left))
    return check(root.left, root.right) if root else True

10.4 迭代遍历

递归本质上用了系统调用栈。我们可以用显式栈模拟，写出迭代版本：

# 前序遍历（迭代）
def preorder_iterative(root):
    if not root:
        return []
    result = []
    stack = [root]
    while stack:
        node = stack.pop()
        result.append(node.val)
        # 先压右再压左，这样左先出栈
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)
    return result

# 中序遍历（迭代）— 最常考
def inorder_iterative(root):
    result = []
    stack = []
    curr = root
    while curr or stack:
        # 一路向左走到底
        while curr:
            stack.append(curr)
            curr = curr.left
        # 弹出栈顶（最左边的节点）
        curr = stack.pop()
        result.append(curr.val)
        # 转向右子树
        curr = curr.right
    return result

# 后序遍历（迭代）— 前序反转法
def postorder_iterative(root):
    if not root:
        return []
    result = []
    stack = [root]
    while stack:
        node = stack.pop()
        result.append(node.val)
        # 注意：先左后右（和前序相反）
        if node.left:
            stack.append(node.left)
        if node.right:
            stack.append(node.right)
    return result[::-1]  # 反转得到后序

面试中：如果面试官要求"不用递归实现中序遍历"，上面的 inorder_iterative 是标准答案。理解它的关键是：用栈模拟递归的"先往左走到底，再处理当前节点，再转向右子树"的过程。

10.5 常见错误

错误 1：忘记处理空节点

# 错误：root 为 None 时会报错
def bad_depth(root):
    return max(bad_depth(root.left), bad_depth(root.right)) + 1

# 正确：先检查 None
def good_depth(root):
    if not root:
        return 0
    return max(good_depth(root.left), good_depth(root.right)) + 1

错误 2：混淆"深度"和"高度"

• 深度（depth）：从根到该节点，自顶向下
• 高度（height）：从该节点到最远叶子，自底向上
• 根的深度 = 0，根的高度 = 树的高度

错误 3：在递归中创建大量列表

# 慢：每次递归创建新列表，总共 O(n²)
def preorder_slow(root):
    if not root:
        return []
    return [root.val] + preorder_slow(root.left) + preorder_slow(root.right)

# 快：用辅助参数收集结果，O(n)
def preorder_fast(root):
    result = []
    def dfs(node):
        if not node:
            return
        result.append(node.val)
        dfs(node.left)
        dfs(node.right)
    dfs(root)
    return result

Level 2 · 它是怎么运行的

10.6 Morris 遍历：O(1) 空间的遍历

递归和迭代遍历都需要 O(h) 的额外空间（h 是树的高度，最坏 O(n)）。Morris 遍历（J. H. Morris, 1979）利用叶子节点的空指针实现 O(1) 空间遍历。

核心思想：用叶子节点的右指针作为"线索"（thread），临时指回其中序后继，遍历完后恢复。

def morris_inorder(root):
    result = []
    curr = root
    while curr:
        if not curr.left:
            # 没有左子树，直接访问当前节点
            result.append(curr.val)
            curr = curr.right
        else:
            # 找到左子树的最右节点（中序前驱）
            pred = curr.left
            while pred.right and pred.right != curr:
                pred = pred.right

            if not pred.right:
                # 第一次到达：建立线索
                pred.right = curr  # 临时指向当前节点
                curr = curr.left
            else:
                # 第二次到达：拆除线索，访问当前节点
                pred.right = None  # 恢复原状
                result.append(curr.val)
                curr = curr.right
    return result

工作过程（以中序遍历为例）：

1. 如果当前节点没有左子树，访问它，走向右子树
2. 如果有左子树，找到左子树的最右节点（中序前驱）
3. 如果前驱的右指针为空，建立线索（指向当前节点），走向左子树
4. 如果前驱的右指针已经指向当前节点（第二次访问），拆除线索，访问当前节点，走向右子树

复杂度：时间 O(n)（每个节点最多被访问 3 次），空间 O(1)（不需要栈或递归）。

缺点：临时修改树结构，不适用于只读场景或并发环境。

10.7 从遍历序列重建二叉树

经典问题：给定前序和中序遍历结果，重建二叉树。

def build_tree(preorder, inorder):
    if not preorder:
        return None

    # 前序的第一个元素是根
    root_val = preorder[0]
    root = TreeNode(root_val)

    # 在中序中找到根的位置，左边是左子树，右边是右子树
    mid = inorder.index(root_val)

    root.left = build_tree(preorder[1:mid+1], inorder[:mid])
    root.right = build_tree(preorder[mid+1:], inorder[mid+1:])
    return root

优化：inorder.index() 每次是 O(n)，总复杂度 O(n²)。用哈希表预存位置，降到 O(n)：

def build_tree_optimized(preorder, inorder):
    idx_map = {val: i for i, val in enumerate(inorder)}
    pre_iter = iter(preorder)

    def helper(lo, hi):
        if lo > hi:
            return None
        root_val = next(pre_iter)
        root = TreeNode(root_val)
        mid = idx_map[root_val]
        root.left = helper(lo, mid - 1)
        root.right = helper(mid + 1, hi)
        return root

    return helper(0, len(inorder) - 1)

哪些组合能唯一确定一棵二叉树？

10.8 序列化与反序列化

将二叉树转为字符串（序列化），再从字符串还原（反序列化）。这在网络传输、持久化存储中很常见。

class Codec:
    def serialize(self, root):
        """前序遍历，空节点用 '#' 表示"""
        vals = []
        def dfs(node):
            if not node:
                vals.append('#')
                return
            vals.append(str(node.val))
            dfs(node.left)
            dfs(node.right)
        dfs(root)
        return ','.join(vals)

    def deserialize(self, data):
        vals = iter(data.split(','))
        def dfs():
            val = next(vals)
            if val == '#':
                return None
            node = TreeNode(int(val))
            node.left = dfs()
            node.right = dfs()
            return node
        return dfs()

# 使用
codec = Codec()
s = codec.serialize(root)      # "1,2,4,#,#,5,#,#,3,#,#"
new_root = codec.deserialize(s) # 还原出完全相同的树

为什么前序序列化需要记录空节点？ 因为不记录空节点的前序序列无法唯一确定一棵树（需要配合中序）。记录了空节点后，前序序列本身就能唯一确定。

10.9 最近公共祖先（LCA）

给定二叉树中的两个节点 p 和 q，找到它们的最近公共祖先。

def lowest_common_ancestor(root, p, q):
    # 基础情况：到达空节点或找到 p/q
    if not root or root == p or root == q:
        return root

    left = lowest_common_ancestor(root.left, p, q)
    right = lowest_common_ancestor(root.right, p, q)

    # 如果左右都找到了，说明 p 和 q 分布在两侧，当前节点就是 LCA
    if left and right:
        return root
    # 否则 LCA 在非空的那一侧
    return left if left else right

时间 O(n)，空间 O(h)。这道题的优雅之处在于：递归自然地处理了所有情况，不需要任何特殊判断。

面试追问：如果是二叉搜索树（BST），LCA 可以利用排序性质做到更高效：

def lca_bst(root, p, q):
    while root:
        if p.val < root.val and q.val < root.val:
            root = root.left
        elif p.val > root.val and q.val > root.val:
            root = root.right
        else:
            return root

Level 3 · 规范怎么定义的

10.10 二叉树的数学性质

Catalan 数：n 个节点的不同形态的二叉树有 C(n) = C(2n, n) / (n+1) 种。这个数列叫 Catalan 数（Eugène Charles Catalan, 1838）。

前几项：1, 1, 2, 5, 14, 42, 132, 429, ...

递推关系：C(n) = Σ C(i) × C(n-1-i)，i 从 0 到 n-1。含义：左子树有 i 个节点，右子树有 n-1-i 个节点。

Catalan 数还出现在：合法括号序列数、出栈序列数、凸多边形三角剖分数。这些问题在本质上是同构的。

10.11 线索二叉树的历史

Morris 遍历的思想来自线索二叉树（Threaded Binary Tree），最早由 A.J. Perlis 和 C. Thornton 在 1960 年提出。

在 n 个节点的二叉树中，有 n+1 个空指针（证明：n 个节点共 2n 个指针域，其中 n-1 个被边占用，剩 n+1 个空指针）。线索二叉树利用这些空指针存储遍历信息：

• 如果节点的左指针为空，让它指向其中序前驱
• 如果节点的右指针为空，让它指向其中序后继

这样就可以在 O(1) 空间内完成遍历。Joseph Morris 在 1979 年的论文 Traversing Binary Trees Simply and Cheaply 中给出了实用的算法实现。

10.12 表达式树与编译器

二叉树在编译器中用于表示表达式。每个内部节点是运算符，叶子节点是操作数：

        +
       / \
      *   3
     / \
    2   5

表示 (2 * 5) + 3。

• 前序遍历得到前缀表达式（波兰表达式）：+ * 2 5 3
• 中序遍历得到中缀表达式：2 * 5 + 3（需要加括号消除歧义）
• 后序遍历得到后缀表达式（逆波兰表达式）：2 5 * 3 +

编译器的语法分析阶段会将源代码解析为抽象语法树（AST，Abstract Syntax Tree），本质上就是表达式树的推广。Python 的 ast 模块可以查看 AST：

import ast
tree = ast.parse("x = 2 * 5 + 3")
print(ast.dump(tree, indent=2))

Level 4 · 边界与陷阱

10.13 递归深度与栈溢出

Python 默认递归深度限制 1000。对于退化的二叉树（链状），节点数超过 1000 就会栈溢出：

# 构造一棵退化的右链二叉树
root = TreeNode(0)
curr = root
for i in range(1, 1500):
    curr.right = TreeNode(i)
    curr = curr.right

# 递归遍历会爆栈
inorder(root)  # RecursionError: maximum recursion depth exceeded

解决方案：

1. 使用迭代遍历（显式栈）
2. sys.setrecursionlimit(10000) — 临时方案，不推荐
3. Morris 遍历（O(1) 空间）

面试中：如果面试官说"输入规模可能很大"，优先使用迭代方案。

10.14 二叉树 vs N 叉树

面试中偶尔会遇到 N 叉树（每个节点有任意数量的子节点）：

class NaryNode:
    def __init__(self, val=0, children=None):
        self.val = val
        self.children = children or []

# N 叉树的前序遍历
def nary_preorder(root):
    if not root:
        return []
    result = [root.val]
    for child in root.children:
        result.extend(nary_preorder(child))
    return result

# N 叉树的层序遍历
def nary_level_order(root):
    if not root:
        return []
    result = []
    queue = deque([root])
    while queue:
        level = []
        for _ in range(len(queue)):
            node = queue.popleft()
            level.append(node.val)
            queue.extend(node.children)
        result.append(level)
    return result

转换：任何 N 叉树都可以转为二叉树（左孩子右兄弟表示法），这就是第 11 章 BST 的基础。

10.15 面试高频题

题目 1：翻转二叉树（LeetCode #226）

def invert_tree(root):
    if not root:
        return None
    root.left, root.right = root.right, root.left
    invert_tree(root.left)
    invert_tree(root.right)
    return root

这道题有个著名的故事：Homebrew 的作者 Max Howell 因为没做出来被 Google 拒了，他在 Twitter 上吐槽引发了关于"面试是否合理"的大讨论。

题目 2：验证二叉搜索树（LeetCode #98）

def is_valid_bst(root):
    def check(node, lo, hi):
        if not node:
            return True
        if node.val <= lo or node.val >= hi:
            return False
        return check(node.left, lo, node.val) and check(node.right, node.val, hi)
    return check(root, float('-inf'), float('inf'))

常见错误：只检查 node.left.val < node.val < node.right.val 是不够的。BST 要求左子树所有节点都小于根，不只是直接左孩子。

题目 3：二叉树的直径（LeetCode #543）

def diameter_of_binary_tree(root):
    max_d = 0
    def depth(node):
        nonlocal max_d
        if not node:
            return 0
        left = depth(node.left)
        right = depth(node.right)
        max_d = max(max_d, left + right)  # 经过当前节点的最长路径
        return max(left, right) + 1
    depth(root)
    return max_d

题目 4：路径总和 III（LeetCode #437）

from collections import defaultdict

def path_sum(root, target_sum):
    count = 0
    prefix = defaultdict(int)
    prefix[0] = 1  # 空路径

    def dfs(node, curr_sum):
        nonlocal count
        if not node:
            return
        curr_sum += node.val
        # 存在前缀和 = curr_sum - target_sum，说明有一段子路径和为 target
        count += prefix[curr_sum - target_sum]
        prefix[curr_sum] += 1
        dfs(node.left, curr_sum)
        dfs(node.right, curr_sum)
        prefix[curr_sum] -= 1  # 回溯：离开当前节点时撤销

    dfs(root, 0)
    return count

这道题巧妙地结合了前缀和（第 3 章）和哈希表（第 8 章）。在树上做前缀和：如果从根到当前节点的路径和为 curr_sum，而之前某个祖先节点的前缀和为 curr_sum - target，那么这段路径的和就是 target。

10.16 二叉树在工程中的应用

二叉树不是一个孤立的数据结构，它是后续所有树形结构的基础。掌握了本章的递归思维和遍历技巧，后面的 BST、堆、Trie、线段树都是在这个基础上加约束条件。

本章小结

练习题：

1. 用迭代（不用递归）实现后序遍历，不使用"前序反转法"（提示：需要记录上一个访问的节点）。
2. 给定二叉树的层序遍历结果 [3,9,20,null,null,15,7]，画出这棵树并写出前/中/后序遍历结果。
3. 如果只给你前序遍历和后序遍历结果（不给中序），能否唯一确定二叉树？举出反例。
4. 实现一个函数，判断二叉树是否是另一棵树的子树（LeetCode #572）。

下一章预告：第 11 章将在二叉树的基础上加入"排序约束"——二叉搜索树。你会看到为什么 BST 的查找可以做到 O(log n)，为什么朴素 BST 会退化成链表，以及红黑树如何用旋转和变色保持平衡。