树

树

树是支撑文件系统、数据库、编译器以及无数面试题的层级化数据结构。本文件涵盖二叉树、二叉搜索树、平衡树、字典树、线段树、Fenwick 树（树状数组）和并查集，以及遍历模式、递归思维和难度递增的题目。

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

• 解决树问题的核心洞见：大多数树问题都用递归求解。结构本身就是递归的（一棵树是一个根加上两棵子树），所以解法也应该是递归的。掌握了「对左子树求解，对右子树求解，再合并」这个模式，你就能解决绝大多数树问题。

二叉树遍历

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

  • 中序（inorder，左、根、右）：对 BST 来说，这会按排序顺序访问节点。
  • 前序（preorder，根、左、右）：适用于序列化和复制树。
  • 后序（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
​

• 陷阱：上面的递归遍历每一步都因为 + 拼接而产生新 list，是 O(n^2)。为了高效，应该传入一个结果 list 并就地追加：

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 祖先的最低节点。

• 模式：如果 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) 经过本节点的最佳路径是什么（左 + 节点 + 右）？(2) 本节点能向父节点贡献的最佳路径是什么（节点 + max(左, 右)，因为一条路径不能在两层都分叉）？把这两者搞混是最常见的错误。

二叉搜索树（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 边界把这个约束往下传递。

中等：二叉搜索树中第 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，前缀树 prefix tree）**按字符把字符串存进一棵树。每条边代表一个字符，从根到标记节点的路径代表一个被存储的字符串。字典树支持 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

• 题目：给定一个字符棋盘和一组单词，找出所有能通过相邻格子遍历形成的单词。

• 模式：先从单词表构造一棵字典树，再从每个格子出发做 DFS，并用字典树及早剪枝（如果没有单词以当前前缀开头，就停）。

• 陷阱：没有字典树的话，你得对每个单词分别 DFS：O(w \cdot m \cdot n \cdot 4^L)。字典树在单词间共享前缀计算，大幅减少工作量。

并查集（不相交集合）

• **并查集（Union-Find，不相交集合并 Disjoint Set Union，DSU）**追踪一组不相交的集合。两个操作：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 最小生成树、把等价物品分组。

中等：连通分量数

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 树（树状数组）

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

• **Fenwick 树（Fenwick tree，树状数组 Binary Indexed Tree，BIT）**对于前缀和查询加单点更新来说是更简单、更快的替代。它用了一个巧妙的位运算技巧：每个位置存一段部分和，这段的范围由最低位的 1 决定。

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)  # 加上最低位的 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、GCD）时用线段树。

常见陷阱汇总

编程练习（使用 CoLab 或 notebook）

以下题目可在 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（BST 中第 K 小元素）—— 中序遍历
• Lowest Common Ancestor of a BST（BST 的最近公共祖先）—— 利用 BST 的有序性

字典树

• Implement Trie（实现字典树）—— 基础字典树操作
• Design Add and Search Words（添加与搜索单词）—— 字典树 + 带通配符的 DFS
• Word Search II（单词搜索 II）—— 字典树引导的回溯

并查集

• Number of Connected Components（连通分量数）—— 基础并查集
• Redundant Connection（冗余连接）—— 用并查集做环检测