树

树是支撑文件系统、数据库、编译器和无数面试题的分层数据结构。本文件涵盖二叉树、BST、平衡树、Trie、线段树、Fenwick树和并查集，包含遍历模式、递归思维以及逐级递增难度的题目。

• 树是一个连通且无环的图（第13章）。最重要的变体是二叉树：每个节点最多有两个子节点（左和右）。树无处不在：编译器中的解析树、浏览器中的DOM树、ML中的决策树，以及数据库中的B树。

• 树问题的关键洞见：大多数树问题通过递归解决。结构本身就是递归的（一棵树由一个根和两棵子树组成），所以解法也应该是递归的。掌握"解左子树，解右子树，合并"的模式，就能解决大多数树问题。

二叉树遍历

• 有四种标准方式访问每个节点：

  • 中序（左，根，右）：对于BST，按排序顺序访问节点。
  • 前序（根，左，右）：用于序列化和复制树。
  • 后序（左，右，根）：用于删除和计算大小。
  • 层序（BFS）：使用队列逐层访问节点。

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

def inorder(root):
    if not root:
        return []
    return inorder(root.left) + [root.val] + inorder(root.right)

def preorder(root):
    if not root:
        return []
    return [root.val] + preorder(root.left) + preorder(root.right)

def postorder(root):
    if not root:
        return []
    return postorder(root.left) + postorder(root.right) + [root.val]

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

• 陷阱：上面的递归遍历在每一步都创建新列表（由于 + 连接），这是 \(O(n^2)\) 的。为了提高效率，传递一个结果列表并原地追加：

def inorder_efficient(root, result=None):
    if result is None:
        result = []
    if root:
        inorder_efficient(root.left, result)
        result.append(root.val)
        inorder_efficient(root.right, result)
    return result

简单：二叉树最大深度

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

• 递归模式：基本情况（null → 0），递归子节点，合并（1 + max）。这一模式适用于数十个树问题。

简单：翻转二叉树

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

中等：最近公共祖先（LCA）

• 问题：找到同时是 \(p\) 和 \(q\) 的祖先的最低节点。

• 模式：如果 \(p\) 和 \(q\) 都在左子树中，LCA在左子树中。如果都在右子树中，LCA在右子树中。如果它们分别在不同子树（一个在左，一个在右），当前节点就是LCA。

def lowest_common_ancestor(root, 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)

    if left and right:
        return root  # p and q are in different subtrees
    return left if left else right

• 陷阱：这假设 \(p\) 和 \(q\) 都存在于树中。如果它们可能不存在，你需要额外的检查。

困难：二叉树中的最大路径和

• 问题：找到任意两个节点之间的最大路径和（路径不需要经过根节点）。

def max_path_sum(root):
    best = [float('-inf')]

    def dfs(node):
        if not node:
            return 0
        left = max(dfs(node.left), 0)   # 忽略负值路径
        right = max(dfs(node.right), 0)

        # 经过此节点的路径（可能作为"折弯点"）
        best[0] = max(best[0], node.val + left + right)

        # 返回此节点可以贡献给其父节点的最大增益
        return node.val + max(left, right)

    dfs(root)
    return best[0]

• 关键洞见：在每个节点，有两个问题：(1) 经过此节点的最佳路径是什么（左 + 节点 + 右）？(2) 此节点可以贡献给其父节点的最佳路径是什么（节点 + max(左, 右)，因为路径不能在两个层级分叉）？混淆这两个是最常见的错误。

二叉搜索树（BST）

• BST满足：对于每个节点，其左子树中的所有值都较小，右子树中的所有值都较大。这使搜索、插入和删除操作（当平衡时）达到 \(O(\log n)\)。

def search_bst(root, target):
    if not root:
        return None
    if target < root.val:
        return search_bst(root.left, target)
    elif target > root.val:
        return search_bst(root.right, target)
    else:
        return root

def insert_bst(root, val):
    if not root:
        return TreeNode(val)
    if val < root.val:
        root.left = insert_bst(root.left, val)
    else:
        root.right = insert_bst(root.right, val)
    return root

• 陷阱：BST操作仅在树平衡时为 \(O(\log n)\)。从排序插入构建的BST退化为链表：每次操作 \(O(n)\)。这就是平衡BST（AVL、红黑树）存在的原因。

中等：验证二叉搜索树

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

• 陷阱：仅检查 left.val < root.val < right.val 是错误的。约束是左子树中所有节点都更小，而不仅仅是直接子节点。lo/hi 边界将此约束向下传播。

中等：BST中第K小的元素

• 模式：BST的中序遍历按排序顺序访问节点。第 \(k\) 个访问的节点就是答案。

def kth_smallest(root, k):
    count = [0]
    result = [None]

    def inorder(node):
        if not node or result[0] is not None:
            return
        inorder(node.left)
        count[0] += 1
        if count[0] == k:
            result[0] = node.val
            return
        inorder(node.right)

    inorder(root)
    return result[0]

Trie（前缀树）

• Trie按字符逐字符地存储字符串在一棵树中。每条边代表一个字符，从根到已标记节点的路径代表已存储的字符串。Trie使得查找复杂度为 \(O(L)\)，其中 \(L\) 是字符串长度，与存储了多少字符串无关。

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end = True

    def search(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                return False
            node = node.children[char]
        return node.is_end

    def starts_with(self, prefix):
        node = self.root
        for char in prefix:
            if char not in node.children:
                return False
            node = node.children[char]
        return True

• 何时使用：自动补全、拼写检查、文字游戏、IP路由表。每当需要基于前缀的操作时。

困难：单词搜索 II

• 问题：给定一个字符面板和一个单词列表，找出所有可以通过遍历相邻单元格形成的单词。

• 模式：从单词列表构建trie，然后从每个单元格进行DFS，使用trie提前剪枝（如果没有单词以当前前缀开头，则停止）。

• 陷阱：没有trie，你需要对每个单词分别进行DFS：\(O(w \cdot m \cdot n \cdot 4^L)\)。trie在单词之间共享前缀计算，大幅减少工作量。

并查集（Disjoint Set Union）

• 并查集维护一组不相交的集合。两个操作：find(x) 返回 \(x\) 所在集合的代表元，union(x, y) 合并包含 \(x\) 和 \(y\) 的集合。

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
        self.count = n  # 连通分量数量

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # 路径压缩
        return self.parent[x]

    def union(self, x, y):
        rx, ry = self.find(x), self.find(y)
        if rx == ry:
            return False  # 已连通
        # 按秩合并
        if self.rank[rx] < self.rank[ry]:
            rx, ry = ry, rx
        self.parent[ry] = rx
        if self.rank[rx] == self.rank[ry]:
            self.rank[rx] += 1
        self.count -= 1
        return True

• 通过路径压缩和按秩合并，两个操作都达到 \(O(\alpha(n)) \approx O(1)\) 的摊还复杂度（反阿克曼函数，实际上是常数级）。

• 何时使用：连通分量、无向图环检测、Kruskal的MST、等价项分组。

中等：连通分量数量

def count_components(n, edges):
    uf = UnionFind(n)
    for u, v in edges:
        uf.union(u, v)
    return uf.count

中等：冗余连接

• 问题：找到那条，当它被移除时，能使图成为一棵树（即创建环的边）。

• 模式：逐条处理边。第一条端点已在同一分量中的边会创建环。

def find_redundant(edges):
    uf = UnionFind(len(edges) + 1)
    for u, v in edges:
        if not uf.union(u, v):
            return [u, v]  # 已连通 → 此边创建环

线段树和Fenwick树

• 线段树回答区间查询（子数组的和、最小值、最大值）并支持点更新，两者都是 \(O(\log n)\)。

• Fenwick树（树状数组/Binary Indexed Trees）是前缀和查询和点更新的更简单、更快的替代方案。它使用巧妙的位运算技巧：每个位置存储一个由最低有效位确定的区间范围的部分和。

class FenwickTree:
    def __init__(self, n):
        self.n = n
        self.tree = [0] * (n + 1)

    def update(self, i, delta):
        i += 1  # 1索引
        while i <= self.n:
            self.tree[i] += delta
            i += i & (-i)  # 加上最低有效位

    def prefix_sum(self, i):
        i += 1
        total = 0
        while i > 0:
            total += self.tree[i]
            i -= i & (-i)  # 移除最低有效位
        return total

    def range_sum(self, l, r):
        return self.prefix_sum(r) - (self.prefix_sum(l - 1) if l > 0 else 0)

• 何时使用：需要带更新的重复区间查询的问题。当只需前缀和时优先使用Fenwick树；当需要任意区间操作（最小值、最大值、GCD）时使用线段树。

---

常见陷阱总结

陷阱	示例	修复
仅检查BST的直接子节点	left.val < root.val 漏掉了更深层的违规	传递 lo/hi 边界
递归中的 \(O(n^2)\) 列表连接	inorder(left) + [val] + inorder(right)	追加到共享列表
忘记基本情况	对空树的无限递归	if not root: return
混淆"经过节点路径"与"传给父节点路径"	最大路径和：在两个层级分叉	返回单分支给父节点，单独跟踪双分支
Fenwick树 1索引 vs 0索引	树数组差一错误	在入口处始终 i += 1
并查集无路径压缩	最坏情况下每次 find 为 \(O(n)\)	self.parent[x] = self.find(self.parent[x])

---

课后习题 (NeetCode)

二叉树模式

• 翻转二叉树 — 基础递归
• 二叉树最大深度 — 递归深度
• 相同的树 — 同步遍历
• 另一棵树的子树 — 嵌套递归
• 二叉树层序遍历 — BFS带层级跟踪
• 二叉树最大路径和 — DFS带全局最优
• 二叉树的序列化与反序列化 — 前序 + null标记

BST模式

• 验证二叉搜索树 — 边界传播
• BST中第K小的元素 — 中序遍历
• BST的最近公共祖先 — 利用BST有序性

Trie

• 实现Trie — 基础trie操作
• 设计添加与搜索单词 — trie + 带通配符的DFS
• 单词搜索 II — trie引导的回溯

并查集

• 连通分量数量 — 基础并查集
• 冗余连接 — 通过并查集检测环