树¶

一句话总结：树是文件系统、数据库、编译器背后的层次结构；本节讲二叉树、二叉搜索树、字典树、线段树、Fenwick 树与并查集，以及它们的遍历、递归模板和由浅入深的题目。

树 (tree) 是文件系统、数据库、编译器以及无数面试题背后的层次数据结构。本节覆盖二叉树、二叉搜索树 (Binary Search Tree, BST)、平衡树、字典树 (trie)、线段树、Fenwick 树与并查集 (Union-Find)，包含遍历模式、递归思路以及难度递增的题目.

树是一个连通且无环的图 (见第 13 章). 最重要的变体是二叉树：每个节点最多有两个孩子 (左孩子与右孩子). 树无处不在：编译器里的语法树、浏览器里的文档对象模型 (Document Object Model, DOM) 树、机器学习里的决策树、数据库里的 B 树。
处理树问题的关键洞察：绝大多数树问题都用递归解决. 结构本身是递归的 (一棵树 = 一个根 + 两棵子树)，解法也就顺势递归。把"解左子树、解右子树、合并结果"这个模板练熟，大多数树题都能拿下。

二叉树遍历¶

访问树的每个节点有四种标准方式:
- 中序 (左，根，右)：对 BST 而言，中序遍历按有序顺序访问节点。
- 前序 (根，左，右)：用于序列化和树的拷贝。
- 后序 (左，右，根)：用于删除节点和计算子树大小。
- 层序 (广度优先搜索 (Breadth-First Search, 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))

递归模板：基线 (空 → 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

中等：最近公共祖先¶

问题：找出 \(p\) 和 \(q\) 的最近公共祖先 (Lowest Common Ancestor, LCA).
模式：如果 \(p\) 和 \(q\) 都在左子树，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 和 q 分别在两棵子树
    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) 穿过当前节点的最优路径是多少 (left + node + right)? (2) 当前节点能贡献给父节点的最优路径是多少 (node + max(left, right)，因为一条路径不能在两层里分叉)? 把这两件事混为一谈，是最常见的错误。

二叉搜索树 (BST)¶

二叉搜索树 (Binary Search Tree, 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]

工业界的平衡结构：跳表、红黑树、B+ 树¶

BST 想在工业界跑起来，必须解决"退化成链表"的问题。下面三种结构是生产系统里最常见的三种平衡方案，各有各的战场。

跳表 (Skip List): Redis zset 背后¶

跳表 (Skip List) 严格来说不是树，而是平衡 BST 的"等效竞品"：平均 \(O(\log n)\) 的查找、插入、删除，但实现比红黑树简单一大截。
想象一个多层有序链表。底层存全部元素，每一层是下一层的随机抽样 (每个节点以概率 \(p\)，通常 \(p=1/2\) 或 \(1/4\)，独立"晋升"到上一层). 查询从最高层往右走，用高层跳过大段区间，底层做精细定位。
谁在用: Redis 的有序集合 (sorted set，简称 zset) 内部就是跳表 + 哈希表的组合。 Redis 作者 antirez 明确解释过为什么选跳表而不是红黑树：实现简单几倍、天然支持范围查询 (ZRANGEBYSCORE)、内存布局对 CPU 缓存更友好 ¹.
陷阱：层数由随机数决定，单次操作最坏 \(O(n)\)；但摊到大量操作上期望是 \(O(\log n)\)，且方差很小，工程上够用。

红黑树 (Red-Black Tree, RB-Tree): Linux CFS 与 C++ std::map¶

红黑树 (Red-Black Tree, RB-Tree) 是自平衡 BST 的代表：每个节点染红或黑，通过 5 条着色约束保证从根到叶的最长路径不超过最短路径的 2 倍，树高 \(O(\log n)\).
相比更严格的 AVL 树，红黑树的平衡条件更"松"，插入/删除需要的旋转更少，查询稍慢一点点——工程上更均衡，也就更受欢迎。
谁在用:
- Linux 内核的 CFS (Completely Fair Scheduler) 用红黑树按虚拟运行时间 (vruntime) 组织可运行进程，每次调度只取最左节点 (vruntime 最小者) 上 CPU ².
- C++ STL 的 std::map / std::set / std::multimap 底层实现就是红黑树。
- Java TreeMap / TreeSet；且 Java 8 的 HashMap 在桶内链表长度超过 8 时会转成红黑树，防止哈希碰撞攻击。
面试期望：手写红黑树代码量大且容易错，面试通常只让你说清"5 条颜色性质 + 插入/删除大致靠旋转和重染色维持平衡"，不要求手撕。

B 树与 B+ 树：MySQL InnoDB 的索引¶

B 树 (B-Tree) 是多路平衡搜索树：每个节点存 \(t-1\) 到 \(2t-1\) 个 key，高度 \(O(\log_t n)\). 分支因子 \(t\) 通常几百甚至上千，让树非常"矮胖".
B+ 树 (B+ Tree) 是 B 树的常用变体：所有实际数据只放在叶子节点，内部节点只存索引 key；所有叶子之间用双向链表串起来，范围扫描顺着叶子链一路遍历，不用回退到父节点。
谁在用:
- MySQL InnoDB 存储引擎的主键索引 (聚簇索引) 和二级索引都是 B+ 树 ³. 默认页大小 16 KB，单页几百个 key；三层 B+ 树就能索引亿级记录，每次点查询只需 2-3 次磁盘 I/O.
- PostgreSQL 默认索引类型 btree 实际也是 B+ 树变体。
- 文件系统：NTFS、HFS+、ext4 目录索引都用 B/B+ 树。
为什么不用红黑树：红黑树是二叉的，高度是 \(\log_2 n\)；数据库要落到磁盘，一次 I/O 读一页 (常见 4 KB / 16 KB)，二叉树每层一次 I/O，亿级数据要 ~30 次 I/O. 多路的 B+ 树把 30 层压到 3 层，I/O 数量骤降。 核心洞察：内存里用二叉平衡树 (红黑树、AVL)，磁盘上用多路平衡树 (B+ 树)，差异全在 I/O 成本。

字典树 (前缀树)¶

字典树 (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¶

问题：给一块字符棋盘和一份单词表，找出所有可以通过遍历相邻格子拼出来的单词。
模式：从单词表建一棵字典树，然后从每个格子出发做深度优先搜索 (Depth-First Search, DFS)，用字典树提前剪枝 (如果没有单词以当前前缀开头，立即停止).
陷阱：不用字典树的话，你得对每个单词单独 DFS: \(O(w \cdot m \cdot n \cdot 4^L)\). 字典树让所有单词共享前缀计算，工作量骤降。

并查集 (不相交集合)¶

并查集 (Union-Find) 维护一族互不相交的集合。两个操作：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)\) (反 Ackermann 函数，实际近似常数).
什么时候用：连通分量、无向图环检测、Kruskal 最小生成树 (Minimum Spanning Tree, 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 Tree，也叫树状数组) 是更简单更快的替代品，专门做前缀和查询与单点更新。它用了一个巧妙的位操作技巧：每个位置存的部分和覆盖一段区间，区间大小由该下标最低位的 1 决定。

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

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

    def prefix_sum(self, i):
        i += 1
        total = 0
        while i > 0:
            total += self.tree[i]
            i -= i & (-i)  # 减去最低位的 1
        return total

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

什么时候用：需要反复做带更新的区间查询。只需要前缀和就用 Fenwick 树；需要任意区间操作 (min、max、最大公约数 (Greatest Common Divisor, GCD)) 就用线段树。

常见陷阱汇总¶

陷阱	示例	修正
BST 只检查直接子节点	`left.val < root.val` 漏掉更深的违规	传 `lo`/`hi` 边界
递归里 \(O(n^2)\) 的列表拼接	`inorder(left) + [val] + inorder(right)`	追加到共享列表
忘记基线	空树时无限递归	`if not root: return`
混淆穿过路径与传给父节点的路径	最大路径和：在两层都分叉	传给父节点只返回单侧，双侧路径单独跟踪
Fenwick 1-index 与 0-index	树数组差一	入口处一律 `i += 1`
并查集不做路径压缩	最坏情况每次 find 都是 \(O(n)\)	`self.parent[x] = self.find(self.parent[x])`

课后练习题 (NeetCode)¶

二叉树套路¶

Invert Binary Tree — 基础递归
Maximum Depth of Binary Tree — 递归求深度
Same Tree — 双树同步遍历
Subtree of Another Tree — 嵌套递归
Binary Tree Level Order Traversal — 带层号的 BFS
Binary Tree Maximum Path Sum — DFS + 全局最优
Serialize and Deserialize Binary Tree — 前序 + 空标记

BST 套路¶

Validate Binary Search Tree — 边界传播
Kth Smallest Element in a BST — 中序遍历
Lowest Common Ancestor of a BST — 利用 BST 有序性

字典树¶

Implement Trie — 字典树基本操作
Design Add and Search Words — 字典树 + 带通配符的 DFS
Word Search II — 字典树引导的回溯

并查集¶

Number of Connected Components — 基础并查集
Redundant Connection — 用并查集检测环

📌 本节要点¶

树的递归本质：一棵树 = 根 + 两棵子树，解法也顺势"左子树 + 右子树 + 合并"三段式。
四种遍历：中序 (左根右，BST 得有序序列)、前序 (根左右，序列化)、后序 (左右根，删除/求大小)、层序 (BFS，按层).
BST 关键性质：左小右大，平衡时 \(O(\log n)\)；有序插入会退化成链表，所以才有 AVL、红黑树等平衡结构。
工业界三大平衡结构：跳表 (Redis zset)、红黑树 (Linux CFS 调度、C++ std::map、Java TreeMap)、B+ 树 (MySQL InnoDB 索引)；内存用二叉平衡，磁盘用多路平衡，差异在 I/O 成本。
验证 BST：必须传 lo/hi 边界，只比较直接父子会漏掉深层违规。
最大路径和的两条路：穿过当前节点的路径 (双分支) 与传给父节点的路径 (单分支) 要分开跟踪。
字典树：以字符为边存字符串，查找 \(O(L)\) 与字符串数量无关；前缀操作、自动补全的首选。
并查集三件套: find + union + 路径压缩 + 按秩合并，均摊 \(O(\alpha(n))\) 近似常数。
区间数据结构：线段树支持任意区间操作；Fenwick 树只做前缀和/单点更新，但更简单更快。
递归遍历性能坑：用 + 拼接列表是 \(O(n^2)\)；改为传共享列表原地追加变成 \(O(n)\).
并查集与图：连通分量、无向图环检测、Kruskal 最小生成树都靠它。

Pugh, W. "Skip Lists: A Probabilistic Alternative to Balanced Trees." Communications of the ACM, 1990. Redis 官方说明见 https://redis.io/docs/latest/develop/data-types/sorted-sets/. ↩
Linux Kernel Documentation, "CFS Scheduler." https://www.kernel.org/doc/html/latest/scheduler/sched-design-CFS.html. ↩
MySQL 8.0 Reference Manual, "The Physical Structure of an InnoDB Index." https://dev.mysql.com/doc/refman/8.0/en/innodb-physical-structure.html. ↩