树与堆
树与堆都属于非线性结构。树强调递归、层级关系和子问题建模；堆强调“局部最值”的快速维护。它们经常出现在遍历、搜索、优先级调度和 top-k 问题里。
概念
- 树处理的是层级关系和子问题拆分，堆处理的是局部最值维护。
- 树题很多时候不是直接算答案，而是先定义递归函数返回什么。
- 堆题很多时候不是排序，而是持续维护当前最值或 top-k。
怎么处理
- 树题先判断是遍历问题、路径问题还是递归返回值问题。
- 写递归前先说清函数语义和返回值含义。
- 如果题目不断要求“当前最小 / 最大 / 前 k 个”，优先想堆。
- 如果题目涉及连接关系变化，再判断是不是并查集或 Trie 这类扩展结构。
树递归的两种思维（看到树题先在这两个里选）
所有二叉树递归题本质都能划进这两类思维，选错会让代码复杂度反常增加：
| 思维 | 何时用 | 代码骨架 | 典型题 |
|---|---|---|---|
| 分解法（后序 / “你给我，我给你”） | 当前节点的答案 = f(左子树答案, 右子树答案) | 先递归左右获取结果，再合并 | 最大深度、直径、判是否平衡、合并二叉树 |
| 遍历法（前序 + 外部状态） | 必须携带路径/父亲/深度等路上信息 | 进递归前更新状态，退出时回溯 | 路径总和、路径打印、反转二叉树 |
快速判断口诀：
- 问“整棵树的某个指标” → 分解法（递归返回值就是子问题答案）
- 问“从根到某节点 / 某些路径 / 与祖先有关的信息” → 遍历法（递归函数返回 void，靠全局变量收集）
- 两者可以混用，但先选一个主调
典型实例
| 专题 | 先看什么 |
|---|---|
| 二叉树 | 先把遍历、递归和层序处理讲清楚 |
| 二叉搜索树 | 看有序性如何减少搜索范围 |
| 堆与优先队列 | 看 top-k 和局部最值如何维护 |
| Trie 字典树 | 看前缀问题如何建模 |
| 并查集 | 看连通性问题如何处理 |
工程实战题
| 专题 | 先看什么 |
|---|---|
| 数据流中位数（工程） | 双堆配合 — 金融/监控 p50/p99 分位数场景 |
| 跳表 SkipList（工程） | Redis ZSet / ConcurrentSkipListMap / LevelDB MemTable 的核心 |
| Radix Tree（压缩 Trie，工程） | URL / IP 路由表等工程场景为何不用裸 Trie |
| Merkle Tree（工程） | Git / 区块链 / IPFS / S3 / Dynamo 反熵的底层 |
| 搜索自动补全 LC642（工程） | Trie + Top-K + 频次——谷歌搜索框 / IDE 补全 / Lucene Suggester 统一底层 |
| 任务调度器 LC621+Cron（工程） | 贪心 + 堆桌面 + 时间轮 + 分布式（Quartz / XXL-Job / Airflow） |
| 撮合引擎（工程） | 交易所订单簿，Price-Time Priority 核心结构 |
看到什么就先想到这类
- 出现“父子层级、路径、子树、遍历”。
- 出现“前 k 个、实时最小 / 最大”。
- 出现“前缀匹配、集合合并、连通块”。