Trees¶

tree 是支撑文件系统、数据库、编译器及大量面试题的层次化数据结构。本文件覆盖 binary tree、BST、balanced tree、trie、segment tree、Fenwick tree 与 Union-Find，并给出遍历模式、递归思维与由浅入深的问题路径。

tree 是 connected 且无环的 graph（见第 13 章）。最重要的变体是 binary tree：每个 node 最多有两个 child（left/right）。tree 几乎无处不在：编译器里的 parse tree、浏览器 DOM tree、ML 中的 decision tree、数据库中的 B-tree。
解决 tree 题的核心洞察是：大多数 tree 问题都应递归求解。因为结构本身就是递归的（tree = root + 左子树 + 右子树），所以解法也应匹配这个结构。掌握“左子树求解、右子树求解、最后合并”的模式，就能覆盖大量题型。

Binary Tree Traversal¶

访问全部 node 的标准方式有四种：
- inorder（left, root, right）：对 BST 来说会得到有序序列。
- preorder（root, left, right）：常用于序列化与拷贝 tree。
- postorder（left, right, root）：常用于删除、计算子树信息。
- level-order（BFS）：按层访问，需配合 queue。

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)\)。更高效写法是传入共享 result 并原地 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

Easy: Maximum Depth of Binary Tree¶

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

递归模板：base case（空节点深度为 0）→ 递归子节点 → 合并（1 + max(...)）。这个模板可迁移到大量 tree 题。

Easy: Invert Binary Tree¶

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¶

问题：找两个 node \(p, q\) 的最近公共祖先（LCA）。
模式：若 \(p,q\) 都在左子树，LCA 在左；都在右子树，LCA 在右；若分居两侧，当前 node 就是 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\) 都存在于 tree 中。若不保证存在，需要额外存在性校验。

Hard: Binary Tree Maximum Path Sum¶

问题：求任意两 node 间路径的最大和（路径不必经过 root）。

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]

关键洞察：每个 node 都有两个问题要区分：(1) 经过该 node 的最优路径（left + node + right）；(2) 该 node 能贡献给父节点的最优“单支”增益（node + max(left, right)）。混淆两者是最常见错误。

Binary Search Tree（BST）¶

BST 性质：对任意 node，左子树所有值更小，右子树所有值更大。在平衡条件下，search/insert/delete 可达 \(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 会退化成 linked list，操作变成 \(O(n)\)。这就是 AVL、red-black tree 存在的原因。

Medium: Validate Binary Search Tree¶

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 是错误的。约束针对整个子树，而非仅直接 child。lo/hi 约束向下传递才能正确覆盖整棵树。

Medium: Kth Smallest Element in a BST¶

模式：BST 的 inorder traversal 给出有序序列，第 \(k\) 个访问到的 node 就是答案。

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）¶

trie 将字符串按字符逐层存入 tree。每条边对应一个字符，从 root 到某个终止标记 node 的路径表示一个已存字符串。查找复杂度为 \(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 路由。凡是前缀查询密集的场景都值得考虑 trie。

Hard: Word Search II¶

问题：给定字符棋盘和单词列表，找出所有可由相邻格子拼出的单词。
模式：先把词表建成 trie，再从每个格子 DFS，同时用 trie 做前缀剪枝（若当前前缀不存在，立刻停止）。
常见坑：若不使用 trie，而是对每个单词单独 DFS，复杂度会接近 \(O(w \cdot m \cdot n \cdot 4^L)\)。trie 能共享公共前缀，显著降本。

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)\)（逆 Ackermann 函数，工程上近似常数）。
适用场景：connected component 统计、undirected graph 环检测、Kruskal 最小生成树、等价类分组。

Medium: Number of Connected Components¶

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

Medium: Redundant Connection¶

问题：找出删掉后可使 graph 重新成为 tree 的那条 edge（即造成环的 edge）。
模式：按顺序处理 edge。第一次遇到两端点已在同一 component 的 edge，就是成环边。

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

Segment Tree 与 Fenwick Tree¶

segment tree 支持区间查询（sum/min/max 等）与单点更新，二者都可做到 \(O(\log n)\)。
Fenwick tree（Binary Indexed Tree）是前缀和场景中更简洁、常数更小的替代方案。核心是位运算技巧：每个位置维护一个由最低位 1（lowbit）决定范围的部分和。

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)

何时选用：若需要频繁“区间查询 + 更新”，可考虑树状结构。只需前缀和时优先 Fenwick tree；若要支持更通用区间操作（min/max/GCD 等），优先 segment tree。

Common Pitfalls Summary¶

Pitfall	Example	Fix
BST 只检查直接 child	`left.val < root.val` 漏掉深层违规	传递 `lo/hi` 边界
递归里频繁列表拼接	`inorder(left)+[val]+inorder(right)`	用共享列表 append
忘记 base case	空树无限递归	先写 `if not root: return`
混淆“穿过节点”与“回传父节点”路径	max path sum 双重分叉错误	回传单分支，双分支只更新全局
Fenwick 下标混乱	0/1 索引错位	入口统一 `i += 1`
Union-Find 无路径压缩	`find` 退化为 \(O(n)\)	`self.parent[x] = self.find(...)`

Take-Home Problems（NeetCode）¶

Binary Tree Pattern¶

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 — preorder + null 标记

BST Pattern¶

Validate Binary Search Tree — 边界传递
Kth Smallest Element in a BST — inorder
Lowest Common Ancestor of a BST — 利用 BST 有序性

Trie¶

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

Union-Find¶

Number of Connected Components — 基础并查集
Redundant Connection — 并查集判环