30 秒速览

  • 什么时候用：树形结构、递归问题、层次关系
  • 核心思维：递归三要素——明确函数定义、确定终止条件、写单层逻辑
  • 遍历方式：前序（根左右）、中序（左根右）、后序（左右根）、层序
  • 时间复杂度：通常 O(n)

一、直觉建立

什么是二叉树？

想象一棵倒过来的树，最上面是树根，往下分叉。每个节点最多分出两个叉（左边一个，右边一个）。

生活中的二叉树：

  • 公司组织架构：CEO → 两个副总裁 → 部门经理
  • 文件夹结构：层层嵌套
  • 家谱树：每个人最多有两个父母

为什么递归在树中如此自然？

核心洞察：树本身就是递归定义的！

一棵树 = 根节点 + 左子树（也是树） + 右子树（也是树）

这就像俄罗斯套娃，大娃娃里套着小娃娃。所以处理树的问题：

  1. 处理根节点
  2. 递归处理左子树（相信它能处理好）
  3. 递归处理右子树（相信它能处理好）

“相信递归”：就像委派任务给下属，你不需要盯着他每一步，只需要告诉他要做什么，相信他能做好。

二、二叉树遍历

前中后序遍历

核心区别：根节点的处理时机

def traverse(root):
    if not root:
        return

    # 前序：根 → 左 → 右
    print(root.val)           # 在这里处理根（第一时间）
    traverse(root.left)
    traverse(root.right)

    # 中序：左 → 根 → 右
    traverse(root.left)
    print(root.val)           # 在这里处理根（中间）
    traverse(root.right)

    # 后序：左 → 右 → 根
    traverse(root.left)
    traverse(root.right)
    print(root.val)           # 在这里处理根（最后）

遍历的应用：

遍历方式应用场景
前序复制树、打印目录结构
中序BST 得到有序序列
后序删除树、计算目录大小

递归实现

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

# 前序遍历
def preorderTraversal(root: TreeNode) -> list[int]:
    result = []

    def traverse(node):
        if not node:
            return
        result.append(node.val)
        traverse(node.left)
        traverse(node.right)

    traverse(root)
    return result

# 中序遍历
def inorderTraversal(root: TreeNode) -> list[int]:
    result = []

    def traverse(node):
        if not node:
            return
        traverse(node.left)
        result.append(node.val)
        traverse(node.right)

    traverse(root)
    return result

# 后序遍历
def postorderTraversal(root: TreeNode) -> list[int]:
    result = []

    def traverse(node):
        if not node:
            return
        traverse(node.left)
        traverse(node.right)
        result.append(node.val)

    traverse(root)
    return result

层序遍历（BFS）

from collections import deque

def levelOrder(root: TreeNode) -> list[list[int]]:
    if not root:
        return []

    result = []
    queue = deque([root])

    while queue:
        level_size = len(queue)
        level = []

        for _ in range(level_size):
            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：LC 104. 二叉树的最大深度

题目：给定一个二叉树，找出其最大深度。

递归思路（后序遍历）

树的深度 = max(左子树深度, 右子树深度) + 1

def maxDepth(root: TreeNode) -> int:
    if not root:
        return 0

    left_depth = maxDepth(root.left)
    right_depth = maxDepth(root.right)

    return max(left_depth, right_depth) + 1

复杂度：时间 O(n)，空间 O(h)，h 是树高

例题 2：LC 226. 翻转二叉树

题目：翻转一棵二叉树。

递归思路

交换左右子树，递归处理。

def invertTree(root: TreeNode) -> TreeNode:
    if not root:
        return None

    # 交换左右子树
    root.left, root.right = root.right, root.left

    # 递归处理
    invertTree(root.left)
    invertTree(root.right)

    return root

复杂度：时间 O(n)，空间 O(h)

例题 3：LC 101. 对称二叉树

题目：给定一个二叉树，检查它是否是镜像对称的。

思路

比较左子树和右子树是否互为镜像。

def isSymmetric(root: TreeNode) -> bool:
    def isMirror(left, right):
        if not left and not right:
            return True
        if not left or not right:
            return False

        return (left.val == right.val and
                isMirror(left.left, right.right) and
                isMirror(left.right, right.left))

    return isMirror(root.left, root.right) if root else True

复杂度：时间 O(n)，空间 O(h)

例题 4：LC 543. 二叉树的直径

题目：给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。

思路

直径 = 左子树最大深度 + 右子树最大深度（不一定经过根节点）

def diameterOfBinaryTree(root: TreeNode) -> int:
    max_diameter = 0

    def depth(node):
        nonlocal max_diameter
        if not node:
            return 0

        left = depth(node.left)
        right = depth(node.right)

        # 更新最大直径
        max_diameter = max(max_diameter, left + right)

        return max(left, right) + 1

    depth(root)
    return max_diameter

复杂度：时间 O(n)，空间 O(h)

例题 5：LC 236. 二叉树的最近公共祖先

题目：给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

思路

后序遍历，找到 p 或 q 就往上传递。

def lowestCommonAncestor(root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
    if not root or root == p or root == q:
        return root

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

    if left and right:
        return root  # p 和 q 分别在左右子树

    return left if left else right  # 都在同一侧

复杂度：时间 O(n)，空间 O(h)

例题 6：LC 124. 二叉树中的最大路径和（Hard）

题目：路径被定义为一条从树中任意节点出发，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。

思路

对于每个节点，最大路径可能是：

  • 只经过左子树的一条路径
  • 只经过右子树的一条路径
  • 经过当前节点，连接左右子树
def maxPathSum(root: TreeNode) -> int:
    max_sum = float('-inf')

    def maxGain(node):
        nonlocal max_sum
        if not node:
            return 0

        # 递归计算左右子树的最大贡献
        left_gain = max(maxGain(node.left), 0)
        right_gain = max(maxGain(node.right), 0)

        # 经过当前节点的最大路径和
        current_path = node.val + left_gain + right_gain
        max_sum = max(max_sum, current_path)

        # 返回当前节点能向上贡献的最大值
        return node.val + max(left_gain, right_gain)

    maxGain(root)
    return max_sum

复杂度：时间 O(n)，空间 O(h)

例题 7：LC 98. 验证二叉搜索树

题目：给定一个二叉树，判断其是否是一个有效的二叉搜索树。

思路一：中序遍历

BST 中序遍历是递增的。

def isValidBST(root: TreeNode) -> bool:
    prev = float('-inf')

    def inorder(node):
        nonlocal prev
        if not node:
            return True

        if not inorder(node.left):
            return False

        if node.val <= prev:
            return False
        prev = node.val

        return inorder(node.right)

    return inorder(root)

思路二：递归验证范围

def isValidBST(root: TreeNode) -> bool:
    def validate(node, low, high):
        if not node:
            return True

        if node.val <= low or node.val >= high:
            return False

        return (validate(node.left, low, node.val) and
                validate(node.right, node.val, high))

    return validate(root, float('-inf'), float('inf'))

复杂度：时间 O(n)，空间 O(h)

例题 8：LC 450. 删除二叉搜索树中的节点

题目：给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。

思路

  1. 找到要删除的节点
  2. 如果节点是叶子，直接删除
  3. 如果节点有一个子节点，用子节点替换
  4. 如果节点有两个子节点，用后继节点（右子树最小值）替换
def deleteNode(root: TreeNode, key: int) -> TreeNode:
    if not root:
        return None

    if key < root.val:
        root.left = deleteNode(root.left, key)
    elif key > root.val:
        root.right = deleteNode(root.right, key)
    else:
        # 找到要删除的节点
        if not root.left:
            return root.right
        if not root.right:
            return root.left

        # 两个子节点都存在，找后继节点
        successor = root.right
        while successor.left:
            successor = successor.left

        root.val = successor.val
        root.right = deleteNode(root.right, successor.val)

    return root

复杂度：时间 O(h)，空间 O(h)

四、递归三要素

要素 1：明确函数定义

def maxDepth(root):
    """返回以 root 为根的树的最大深度"""

要素 2：确定终止条件

if not root:
    return 0  # 空树深度为 0

要素 3：写单层递归逻辑

left = maxDepth(root.left)   # 相信左子树能算出深度
right = maxDepth(root.right) # 相信右子树能算出深度
return max(left, right) + 1  # 当前层的逻辑

五、复盘清单

触发信号

  • 树形结构
  • 层次关系
  • 需要遍历所有节点
  • 需要自底向上/自顶向下处理

边界条件

  • 空树
  • 单节点树
  • 只有左子树/右子树
  • 完全不平衡的树（退化为链表）

常见错误

  • 忘记终止条件（无限递归）
  • 没有处理空节点
  • 递归返回值使用错误

六、题目清单

基础题

题号题目难度考点
104二叉树的最大深度Easy后序遍历
226翻转二叉树Easy前序遍历
101对称二叉树Easy递归比较
102二叉树的层序遍历MediumBFS
257二叉树的所有路径Easy前序遍历

进阶题

题号题目难度考点
236最近公共祖先Medium后序遍历
543二叉树的直径Easy深度计算
124二叉树最大路径和Hard后序遍历
98验证BSTMedium中序遍历/范围验证
450删除BST节点MediumBST 操作
114二叉树展开为链表Medium前序遍历