树、BST 与 Trie · HTML
数学 / 逻辑形态
dfs(node) 对空节点返回 identity；递归取 child summaries，以 combine(value,children) 生成 upward_summary，并可能用两个或多个 child 分支更新 global_answer。
识别信号
- 输入是根树或可建立父子关系的树。
- 节点答案依赖完整子树信息。
- 父节点只需高度、和、边界或单条可延伸路径等小摘要。
- 某个全局结构可能在当前节点连接多个子树。
- 后序遍历自然保证先子后父。
容易误判的相似信号
| Signal | Why it is different |
|---|
| 需要按层或最近深度 | 层序 BFS 更直接，并能在整层边界上处理。 |
| 每节点有多个互斥决策模式 | 一个摘要不够时应升级为 tree DP 的状态向量。 |
| 一般图中的路径聚合 | 环与共享子图破坏独立子树，需 visited、图算法或 DAG DP。 |
核心不变量
dfs(u) 返回的摘要只描述 u 子树且满足父调用契约；返回前，所有完全位于 u 子树的全局候选都已被考虑。
状态、转移与处理顺序
| Item | Definition |
|---|
| State | 当前节点、子递归返回摘要，以及独立的全局 accumulator 或复合返回对象。 |
| Transition | 先递归所有 child，再从其摘要计算节点局部候选、更新全局量，并构造单个向上摘要。 |
| Frontier / order | 递归栈上的 postorder；空节点 identity 使叶子转移统一。 |
Python 骨架
def tree_diameter(root):
best = 0
def height(node):
nonlocal best
if node is None:
return 0
left = height(node.left)
right = height(node.right)
best = max(best, left + right)
return 1 + max(left, right)
height(root)
return best
正确性思路
- 空树高度 0，符合返回契约。
- 归纳假设左右高度正确；经过当前节点向上可延伸的最长链只能选更高一侧，所以返回 1+max。
- 以当前节点为最高连接点的最长路径恰由 left+right 给出；每条跨子树路径在唯一连接点被考虑，global best 正确。
复杂度
| Time | Space | Parameters |
|---|
| O(n)，若每节点 combine 为 O(度数) | O(h) 递归栈，最坏 O(n) | n 为节点数，h 为树高。 |
边界条件
- 空树
- 单节点的边数/节点数定义
- 极深退化树
- 负权时 identity
- 多叉树取前两大 child
- 全局变量跨调用复用
错误模式
| Pattern | Why it fails / fix |
|---|
| 把全局最优整体返回给父节点 | 连接两个子树的路径不能再同时向父延伸；需区分 complete 与 extendable。 |
| preorder 时就计算 | 子树摘要尚未得到，节点聚合不完整。 |
| 空节点 identity 错误 | 高度、和、min/max、负权路径需要不同 neutral/sentinel。 |
| 每节点重新遍历子树 | 将 O(n) 退化成 O(n²)；子信息应一次返回复用。 |
选择与排除规则
- 先写父节点究竟需要 child 返回什么。
- 区分向上可延伸摘要与已完成全局候选。
- 选择与 combine 运算匹配的空节点 identity。
- 深树考虑迭代 postorder。
相关模板
| Relation | Template | Boundary |
|---|
| traversal-foundation | BST 有序性 / 中序遍历 | 需要从子树返回 min/max 或结构摘要。 |
| generalization | 树形 DP | 一个摘要不足，需按节点模式返回多个答案。 |
原创微型例子
| 环节 | 内容 |
|---|
| Result | 完整候选连接两侧，向上摘要只保留一侧，语义不同。 |
| Setup | 根的左链高 2、右链高 1。 |
| Trace | 根处完整跨越路径长度为 2+1=3；向父只能返回 1+max(2,1)=3 的单链高度。 |
Recall prompts
我的补充