树的聚合与路径搜索
一、树算法只有一句话
- 这一篇对应官方 Lecture 15(Trees),把线展开成分叉:树上每个节点可以挂任意多个子树。
链表的递归是「处理 first,递归 rest」,只有一根枝。
树是把「一根枝」换成了「一列枝」:
处理
label,对branches里每一个子树递归,再把结果聚合起来。
认准这句话,树相关的代码大多只是填空。剩下的功夫都在边界上——叶子如何处理、空树怎么办。
二、树是什么
1 | class Tree: |
输出:
1 | Tree(1, [Tree(2, [Tree(4)]), Tree(3)]) |
两处设计值得说道:
branches=list(branches)是防御性拷贝。如果直接写self.branches = branches并让默认值是[],所有「没传 branches 的树」会共享同一个列表对象——改一棵树的子树,别的树跟着变。这是 Python 默认参数最经典的问题,标准写法就是在规避它。- 叶子判据统一走
is_leaf(),而不是到处写len(t.branches) == 0。判据收在一处,边界就收在一处。
三、聚合:节点数与叶子数
1 | class Tree: |
输出:
1 | [Tree(2, [Tree(4)]), Tree(3)] |
这两个函数的差别,是理解树聚合的关键。
| 函数 | 对 t 本身怎么算 |
对 branches 怎么算 |
|---|---|---|
count_nodes |
+1(自己算一个节点) |
对每个 b 求和 |
count_leaves |
叶子才 +1,否则 +0 |
对每个 b 求和 |
count_nodes(t.branches) 这种写法是必错的——branches 是列表,不是 Tree,传进去会 AttributeError。聚合类函数永远是「先对每个 b 求值,再把一列结果聚合」,中间那层 [f(b) for b in t.branches] 一步都不能省。
四、深度与 max([]) 陷阱
1 | class Tree: |
输出:
1 | 3 |
depth 是「聚合」里最需要小心边界的一个:max([...]) 遇到空列表会直接抛错。
1 | class Tree: |
输出:
1 | max([]) 抛错: ValueError |
所以 depth 开头那句 if t.is_leaf(): return 0 不是可选项。少了它,一棵单节点树就会在 max([]) 处报错。
真正的难点在这里:是否主动考虑过空树与叶子?
五、路径搜索:count_paths
树的另一大类题是路径——从根走到叶,问有多少条路满足条件。
1 | class Tree: |
输出:
1 | 1 |
两个值得掌握的手法:
- 「把目标减着往下传」。不要在递归里带一个累加的和,而是每往下一层就
total - t.label,走到叶子时看剩下的目标是不是正好等于叶子的标签。这样参数只有两个,状态干净。 - 只有叶子能判定成败。非叶子节点直接返回「各分支的结果之和」,自己不记数。写成
sum([...])而不是累加循环,是树的通用姿势。
flowchart TB
R["Tree(1)"]
R --> A["Tree(2, [Tree(3)])"]
R --> B["Tree(2)"]
A --> A1["Tree(3)"]
R -.->|"路径和 = 1+2+3 = 6 ✓"| P1["命中"]
R -.->|"路径和 = 1+2 = 3"| P2["不命中"]
P1 -.-> C["count_paths(t, 6) → 1"]
P2 -.-> D["count_paths(t, 3) → 1"]
六、链表去重:改指针的范例
链表是另一类需要就地修改的递归结构。去重的关键在于「边走边改 rest 指针」:
1 | class Link: |
输出:
1 | Link(1, Link(2, Link(3))) |
关键在内层 while:它在 cur 处不动,把后面所有重复节点一次跳完,而不是只跳一个。写成 if 会留下未被跳过的重复节点。改的是 cur.rest(指针),不是 cur.first(值)——插入和删除本质都是在改指针。
七、递归数据结构的操作要点
flowchart TB
R["递归数据结构的操作要点"]
R --> A["树的聚合与路径"]
R --> B["链表的就地修改"]
R --> C["递归函数编写"]
R --> D["边界条件"]
A --> A1["先对每个 b 求值再聚合"]
A --> A2["叶子必须处理 max([]) 的空列表"]
B --> B1["改 rest 指针,不改值"]
B --> B2["先保存 nxt 再掉头"]
C --> C1["信心跃迁"]
C --> C2["参数必须变小"]
D --> D1["Link.empty"]
D --> D2["is_leaf()"]
D --> D3["n < 0 与 m == 0"]
四类操作的要点:
- 树上的聚合与路径搜索——路径和、最大路径、
count_paths的变体。 - 链表的就地修改——去重、反转、拼接、有序插入。
- 递归函数的编写——先手算最小例子,再写递归步骤。
- 多重边界条件——
Link.empty/is_leaf()/n < 0,逐一核对。
书写与调试习惯:先在草稿区画出调用树或环境图,再写代码;写完后立即手工推演一个最小例子(例如单节点树、空链表)。这一步通常能提前暴露边界问题。
八、小结
| 模式 | 骨架 | 验证 |
|---|---|---|
| 节点计数 | 1 + sum([count_nodes(b) for b in t.branches]) |
count_nodes(t) → 4 |
| 叶子计数 | 叶子 +1,否则求和各分支 |
count_leaves(t) → 2 |
| 深度 | 1 + max([...]),叶子先处理 |
depth(t) → 3 |
| 路径计数 | 目标减着往下传,叶子判定 | count_paths(t, 6) → 1 |
| 链表去重 | 内层 while 在原位跳过所有重复 |
1→2→1→3→2 → 1→2→3 |
| 链表反转 | 平行赋值,先记 nxt |
1→2→3 → 3→2→1 |
三条能带走的:
- 树算法只有一句话:对
branches逐个递归,再聚合。 写成count_nodes(t.branches)一定错——branches是列表。 - 叶子必须主动处理。
max([])会抛ValueError,depth里那句is_leaf()不是装饰。 - 三个必须核对的边界:叶子、
Link.empty、递归参数是否真的变小。
本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 HespethornのBlog!

