企业官网建设流程全解析

maths-cs-ai-compendium 树结构深度指南：二叉树遍历、BST、Trie、Union-Find 与 Fenwick 树实战

【免费下载链接】maths-cs-ai-compendiumBecome a cracked AI/ML researcher/engineer with this unconventional textbook covering maths, computing, and ML with intuition.项目地址: https://gitcode.com/GitHub_Trending/mat/maths-cs-ai-compendium

树（Tree）是文件系统、数据库索引、编译器与浏览器背后的层级数据结构，也是算法面试中出现频率最高的主题之一。本文以 maths-cs-ai-compendium 第 14 章「数据结构与算法」中的 树结构章节 为核心，系统讲解二叉树的四种遍历、二叉搜索树（BST）、前缀树（Trie）、并查集（Union-Find）以及线段树 / Fenwick 树的原理与完整可运行的 Python 实现，并结合仓库内离散数学、图论、操作系统、机器学习等章节的交叉证据，帮你建立起「递归三件套 + 模式识别」的树问题解题能力。读完本文，你将能够徒手实现所有树类核心数据结构，并独立解决从 Easy 到 Hard 的典型树问题。

树的本质：递归结构决定递归解法

在进入代码之前，先明确树的数学定义。仓库 第 13 章 · 离散数学 中给出：

• 树是连通且无环的图，等价地，它有 $n$ 个节点和 $n-1$ 条边；
• 有根树指定一个根节点，其余每个节点有且只有一个父节点；
• 生成树包含图的所有节点，而最小生成树（MST）在 图论章节 中被进一步探讨，Kruskal 算法正是通过并查集实现的（后文详述）。

树最重要的变体是二叉树：每个节点至多有两个孩子（左孩子和右孩子）。树的递归定义——「一棵树是一个根节点加两棵子树」——决定了解决树问题的核心心法：

大多数树问题都可以递归求解。掌握「先解左子树、再解右子树、最后合并结果」的模式，就能解决绝大多数树问题。

这个模式与 第 14 章基础篇 中强调的递归三要素完全一致：基准情形（base case，空树返回）、递归情形（把问题分解为更小的子树）、信任递归（trust the recursion，假设递归调用已返回正确答案，只需处理合并逻辑）。文中反复出现的if not root: return ...就是树递归的基准情形。

树在现实世界中无处不在，仓库各章节均有佐证：

二叉树的四种遍历

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

• 中序遍历 Inorder（左、根、右）：对 BST 而言，按升序访问所有节点；
• 前序遍历 Preorder（根、左、右）：适用于序列化（serialisation）与树的复制；
• 后序遍历 Postorder（左、右、根）：适用于删除节点与计算子树大小；
• 层序遍历 Level-order（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)$ 问题。上面三个递归版本在每一步都用+拼接新列表，而 Python 的列表拼接会复制两个列表的内容，总代价为 $O(1 + 2 + \cdots + n) = O(n^2)$。这与 基础篇 中「字符串拼接s += c是 $O(n^2)$」是同一个隐藏代价问题。高效做法是传入共享的结果列表、原地 append：

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

注意result=None的写法——不要用def f(root, result=[])这种可变默认参数，它会让所有调用共享同一个缓存列表（基础篇的 DP 陷阱表同样点名了这个错误）。

层序遍历的要点：for _ in range(len(queue))在进入循环时快照当前层的大小，保证每次迭代处理恰好一层，这是 BFS 分层的标准技巧，与 图论章节的 BFS 模板 中「入队时标记 visited」的原则相辅相成。

递归模式的经典演练

Easy · 二叉树最大深度

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

递归模式：基准情形（空树 → 0）→ 递归孩子 → 合并（1 + max）。这个「base case + recurse on children + combine」的模板适用于几十道树问题，树的高度计算与 基础篇 中height(root)的例子完全同构。

Easy · 翻转二叉树

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

Medium · 最近公共祖先（Lowest Common Ancestor）

问题：找到同时是 $p$ 和 $q$ 祖先的最深节点。

模式：若 $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 and q are in different subtrees return left if left else right

陷阱：该解法假设 $p$ 和 $q$ 都存在于树中。若它们可能不存在，需要在回溯时额外标记「是否真的找到了两个节点」，否则会返回假阳性。

Hard · 二叉树最大路径和

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

def max_path_sum(root): best = [float('-inf')] def dfs(node): if not node: return 0 left = max(dfs(node.left), 0) # ignore negative paths right = max(dfs(node.right), 0) # path through this node (possibly as the "bend") best[0] = max(best[0], node.val + left + right) # return the max gain this node can contribute to its parent return node.val + max(left, right) dfs(root) return best[0]

核心洞察：在每个节点要区分两个问题：(1) 经过该节点的最佳路径（left + node + right，路径在此处「拐弯」）；(2) 该节点能贡献给父节点的最佳路径（node + max(left, right)，因为一条路径不能分叉两层）。混淆这两个量是最常见的错误。这里的dfs返回值与best全局最优解分离的设计，是「后序自底向上 + 全局变量」的经典组合，注意best = [float('-inf')]用列表包装是为了在闭包内可写。

二叉搜索树（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)$ 只在平衡时成立。按有序序列插入会退化成链表，每次操作变为 $O(n)$。这正是 AVL 树、红黑树等平衡 BST存在的原因。仓库 操作系统章节 给出了教科书外的真实案例：Linux 的CFS 调度器维护一棵红黑树（按虚拟运行时间排序的平衡二叉搜索树），每次调度决策 $O(\log n)$；同一章节 还指出 Btrfs/ZFS 与数据库索引使用B 树（平衡搜索树族），这些正是「平衡性」在工业界的直接体现。

Medium · 验证二叉搜索树

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边界把约束沿路径向下传播——这是「边界传播」模式的典型应用，初值float('-inf')/float('inf')代表根节点无约束。

Medium · 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]

优化点：result[0] is not None提前剪枝，找到第 $k$ 小后不再遍历剩余节点；用count = [0]与result = [None]列表包装是为了在闭包中修改变量（Python 闭包对不可变变量只能读不能写）。若需要频繁查询第 $k$ 小，可改用[线段树/平衡树 + 节点计数]的增强版 BST，见后文。

前缀树（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

适用场景：自动补全（autocomplete）、拼写检查、单词游戏、IP 路由表——凡是需要基于前缀的操作都优先考虑 Trie。注意search与starts_with的区别：前者要求路径终点恰好是一个完整单词（is_end为 True），后者只要求前缀路径存在。

Hard · 单词搜索 II

问题：给定字符棋盘和单词列表，找出所有可由相邻格子路径组成的单词。

模式：先用单词列表建 Trie，再从每个格子出发 DFS，用 Trie 尽早剪枝——若当前前缀下没有任何单词（starts_with为假），立即停止该方向。

陷阱：不用 Trie 时需要对每个单词单独 DFS，复杂度为 $O(w \cdot m \cdot n \cdot 4^L)$；Trie 让所有单词共享前缀计算，大幅削减重复工作。这与 基础篇 的「哈希表查找把重复计算转化为 $O(1)$ 查询」是同一思想——用结构共享消灭重复前缀的搜索。

并查集（Union-Find / Disjoint Set Union）

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 # number of connected components def find(self, x): if self.parent[x] != x: self.parent[x] = self.find(self.parent[x]) # path compression return self.parent[x] def union(self, x, y): rx, ry = self.find(x), self.find(y) if rx == ry: return False # already connected # union by rank 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

复杂度：路径压缩（path compression）+ 按秩合并（union by rank）后，两个操作均摊 $O(\alpha(n)) \approx O(1)$（反阿克曼函数，工程上视为常数）。count字段实时追踪连通分量数量，是后文连通分量问题的关键。

适用场景：连通分量、无向图环检测、Kruskal 最小生成树、等价项分组。离散数学章节 明确指出 Kruskal 算法「排序边，贪心加入不产生环的最轻边」，其中「不产生环」的判定正是并查集：若边的两端点已在同一集合，加入该边必成环。而 MST 与 图论章节 的连通性、图算法章节的 DFS 连通分量 互为补充（DFS 递归写法空间 $O(n)$，并查集更省且天然支持动态加边）。

Medium · 连通分量数量

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

逐条 union 所有边后，count就是连通分量数量。这是「动态连通性」的经典场景，与图章节 BFS/DFS 计岛（Number of Islands）是同一问题的两种求解视角。

Medium · 冗余连接（Redundant Connection）

问题：找出那条「删除后图变成树」的边，即产生环的那条边。

模式：逐条处理边，第一条「两端点已在同一分量」的边就是制造环的边。

def find_redundant(edges): uf = UnionFind(len(edges) + 1) for u, v in edges: if not uf.union(u, v): return [u, v] # already connected → this edge creates a cycle

这里UnionFind(len(edges) + 1)是因为节点编号从 1 开始，需要 $n+1$ 个槽位（$n$ 为边数，恰好等于树中节点数）。union 返回False表示两端已连通——该边制造了环，直接返回。

线段树（Segment Tree）与 Fenwick 树（树状数组）

线段树支持区间查询（子数组的 sum、min、max）和单点更新，均为 $O(\log n)$。它把数组递归分成两半，用树节点缓存区间聚合值，查询/更新只需沿树路径访问 $O(\log n)$ 个节点。

**Fenwick 树（二叉索引树 / BIT）**是前缀和查询与单点更新的更简单、更快的替代方案。它利用一个巧妙的位运算技巧：每个位置存储一段「由最低有效位（lowest set bit）决定范围」的部分和。

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) # add lowest set bit def prefix_sum(self, i): i += 1 total = 0 while i > 0: total += self.tree[i] i -= i & (-i) # remove lowest set bit return total def range_sum(self, l, r): return self.prefix_sum(r) - (self.prefix_sum(l - 1) if l > 0 else 0)

位运算直觉：i & (-i)提取整数i的最低有效位。update沿树向上走（i += lowbit），prefix_sum沿树向下走（i -= lowbit），两者都以 $O(\log n)$ 步完成。理解这一点，就不需要死记代码。

何时选哪种：只需前缀和与点更新 → Fenwick 树（代码短、常数小、内存省）；需要任意区间运算（min、max、GCD 等不可逆运算）→ 线段树。二者可视为「静态数组 + 动态更新」场景下的进阶替代，与第 14 章前缀和基础形成从静态到动态的递进。

陷阱（原文档要点）：Fenwick 树的内部数组是 1 索引的，而调用方传入的是 0 索引。update和prefix_sum入口必须统一i += 1，range_sum中l == 0时要避免访问prefix_sum(-1)。漏掉任何一处偏移都会造成 off-by-one 错误。

常见陷阱速查表

此外，结合仓库其他章节还可补充两条实战经验：

• Python 递归深度：默认递归限制约 1000（基础篇 明确提到）。深度树（如退化的 BST）应优先迭代解法（显式栈），或用sys.setrecursionlimit谨慎调高；
• 完全二叉树的数组存储：二叉堆是「父子下标满足 $2i+1$、$2i+2$」的完全二叉树，详见 链表/栈/队列章节的堆部分——它是线段树「树形数组化」思想的近亲，值得对比学习。

课后练习（NeetCode 题单）

以下题目按模式分组，建议按「先看懂模式 → 徒手实现 → 计时训练」的顺序完成（题名与原文档一致，可在 LeetCode/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 有序性

Trie

• Implement Trie — 基础操作
• Design Add and Search Words — Trie + 通配符 DFS
• Word Search II — Trie 引导的回溯

Union-Find

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

小结

本文把 原树章节 的完整知识体系（四种遍历、BST、Trie、Union-Find、线段树/Fenwick 树）全部继承并逐项深化：每段代码都保留了可直接运行的原版实现，同时补充了复杂度分析、隐藏陷阱与仓库内交叉证据——树的数学定义来自离散数学，递归心法来自基础篇，红黑树与 B 树的工业应用来自操作系统，决策树与随机森林见机器学习章节，堆与完全二叉树见链表章节。掌握「基准情形 + 递归子树 + 合并」这一统一模式，配合上述数据结构的选择直觉，你将能从容应对绝大多数树类面试与工程问题。

【免费下载链接】maths-cs-ai-compendiumBecome a cracked AI/ML researcher/engineer with this unconventional textbook covering maths, computing, and ML with intuition.项目地址: https://gitcode.com/GitHub_Trending/mat/maths-cs-ai-compendium