# 参考解 · lab 0017 · 树：会递归的结构

**做完四个任务再打开这里。** 这里的四个 `.py` 与任务目录里的文件同名：
把它们拷进 `lab/0017-binary-tree-traversal/` 覆盖同名文件，再跑 `py run_tests.py`，
应当四个任务全过（本机实测几秒，其中任务 4 的计时自己占一秒多）。

参考解是自包含的：`tools.py` 与 `run_tests.py` 这里各有一份，拷过去直接就能跑。
四个任务都只 `import` 给好的 `tools`，任务之间**不互相 import**（任务 4 自己带
`build_chain` / `build_balanced`），所以拷一个也能跑；四个一起拷最省事。
这与 0010 那套的约定一致。

## 逐个任务看什么

| 任务 | 参考解里补上的关键几行 | 要看的现象 |
| --- | --- | --- |
| 1 · 四种遍历 | 三个递归版都是**累加器**：`out.append(t[0])` 夹在两个递归调用中间/之前/之后；层序用 `q.popleft()` 与 `x[1] is not None` | 示例树前序 `A B D E C F`、中序 `D B E A C F`、后序 `D E B F C A`、层序 `A B C D E F`，与课件四行逐字一致；空树四种都是 `[]`，单点四种都是 `['A']` |
| 2 · 节点数与树高、对称性 | `1 + count(左) + count(右)`；`1 + max(height(左), height(右))`；`is_mirror` 的四个分支，末一行左对右 `a[1]`↔`b[2]`、`a[2]`↔`b[1]` | 那张表五行：空树 `0 0 True`、单点 `1 1 True`、对称树 `5 3 True`、示例树 `6 3 False`、只差一个值 `5 3 False`；`镜像对 是不是镜像 False`（形状相同的两棵树不是互为镜像） |
| 3 · 形状与递归深度 | `build_chain` 一路往左；`build_balanced` 照课件 `left = k // 2`；`height` 不许改成迭代版；`max_safe_depth` 从 `limit - 10` 往上试到第一条爆栈的链，**不改**递归上限 | 平衡 n=100/1000/10000 的树高是 7 / 10 / 14（约 $\log_2 n$）；链状 n=1000 与 n=10000 两行都是**爆栈**；爆栈长度 999、递归再深一层 997（主块顶层直接试能到 998）、固定开销 2-3 层 |
| 4 · 拼接与累加器的代价 | `preorder_concat` 照课件写成 `[t[0]] + 递归 + 递归`；`preorder_acc` 往 `out` 里 append；`best_of` 用 `tools.timed` 跑 `repeats` 次取最小 | 链状 200→400→800：拼接 0.000056 / 0.000187 / 0.000702 秒（链长四倍、涨约 12.5 倍，**平方级**），累加器 0.000012 / 0.000034 / 0.000077 秒（涨约 6.4 倍，接近线性）；链状 n=2000 上拼接比累加器慢 20 倍上下，平衡树上只慢 1.7 倍 |

## 每个任务的「为什么」

- **任务 1**：三个递归遍历只差 `out.append(t[0])` 那一句的位置——前序在最前、
  中序夹在中间、后序在最后。写成累加器之后，**子树内部的顺序仍由同一个函数自己保证**，
  你不需要在脑子里模拟每一层。层序遍历不能写成递归：它要「先访问完第 1 层再访问第 2 层」，
  与栈的次序相反，得用第 10 课的队列；队列里存的是**子树**（一个 `[值, 左, 右]` 列表），
  取出一个就把它的值收进结果、把它存在的孩子从右边排进去。入队前比较写
  `x[1] is not None`——写成 `if x[1]` 的话，值为 `0` 或 `''` 的结点会被悄悄丢掉。
- **任务 2**：四个函数都是「两个孩子交回答案，在根上合并」。`height` 那一行要看清楚：
  左子树交回一个高度、右子树交回一个高度，取较大者再加一（加上根自己这一层）——
  于是整棵树的答案由两个子树的答案拼出来。`is_mirror` 的四个分支缺一个都会算错：
  漏掉「一边空一边不空」那一句就会去取 `None[0]` 而报错。最后一行两个递归的参数
  是**左对右、右对左**；写成左对左判的就是「两棵子树一模一样」，
  例子里的 M1 / M2 正好形状相同，会当场判错。
- **任务 3**：这一份量的是**递归深度**，不是树高本身：同一棵树，递归会走到多深。
  两者在平衡树上接近（1 万个结点只走 14 层），在链状树上差得很远（一千个结点就爆栈）。
  关键结论是那条：**递归深度等于树高，而树高取决于形状、不取决于规模**。
  `max_safe_depth` 之所以要从 `limit` 往下退几层再往上试，是因为 `limit` 本身已经贴着
  上限：它交回的值与 `sys.getrecursionlimit()` 只差 2-3 层固定开销（进入 `height`、
  递归里调用 `max`、解释器自己占的那几层）。这一行**注定差得动一两层**——
  贴着上限试，差的就是一两个栈帧：在函数里试比在主块顶层试少一层（函数自己那一帧），
  所以参考解报 997、而主块里直接试能走到 998。判分接受 995-998 这一小段，
  真正的判据是「它贴着上限，而且那个深度上 `height` 交回的树高**等于深度本身**」。
- **任务 4**：拼接版每一层都要把两个孩子交回的列表复制一遍。链状树上越靠近根，
  子树越大、要复制的总量按平方级涨（链长四倍、时间约十二倍）；平衡树上每个结点的
  子树都不大，所以两版只差 1.7 倍上下。所以这一条判断有两层：收集结果用累加器，
  而且**测性能时不能只测一种形状**。最后一段量的那条链有 2000 层，比默认上限还深，
  所以主块在那一段外面把上限临时调高、`finally` 里还原——那一段要看的是拼接的
  复制量，不是撞递归上限。

## 常见错法（对照自己的写法）

- **漏了 `if t is None` 这个基例**：不会算出一堆错答案，而是当场停下来报
  `TypeError: 'NoneType' object is not subscriptable`；报错位置是第一个叶子那个
  不存在的孩子。看到 `NoneType` 就去想「哪个函数的基例漏了」。
- **层序写成递归**：写不出来就说明走错了方向——层序要队列，不能递归。
- **层序入队比较写 `if x[1]`**：值为 `0` 的结点被丢掉，输出少一截；
  要写 `if x[1] is not None`。
- **层序里把 `x`（子树）换成 `x[0]`（值）入队**：下轮 `popleft` 出来的是个数，
  `x[1]` 直接报 `TypeError: 'int' object is not subscriptable`。
- **中序/后序的 `append` 放错位置**：三个函数几乎一样，只有那一句的位置不同；
  位置错了结果会是一份「看起来很有道理」的顺序（比如中序写成后序的样子）。
- **`is_mirror` 只写两个分支**：漏掉「都空」时 `None` 会一路递归不收敛；
  漏掉「只有一个空」时取 `None[0]` 当场报错。
- **`is_mirror` 写成左对左**：判的是「两棵子树一模一样」，
  形状相同、值不同的两棵树会被判成镜像（M1 与 M2 就是这一组）。
- **`height` 写成迭代版**：任务 3 量的就是递归深度，改成显式栈就量不到了；
  判分会发现「链状树一千层也没爆栈」。
- **在 `height` 里 `try: ... except RecursionError`**：判分靠 RecursionError
  判断爆栈发生在哪一层；函数里接住它，任务 3 那两条线全对不上。
- **`max_safe_depth` 直接交回 `sys.getrecursionlimit()`**：那个值已经贴着上限，
  树高等于它时必爆；要交回「**跑得动**的最大值」。
- **在 `max_safe_depth` 里改递归上限**：这一份量的就是**默认**上限下的那条线；
  改高了量到的就不是它了，判分会发现值与 `sys.getrecursionlimit()` 对不上。
  （任务 4 的最后一段才是刻意临时调高上限的地方，那里量的是耗时。）
- **`max_safe_depth` 差出一大截**：它要贴着上限（本机 995-998）。从 990 那样太远的地方
  停下来，判分看得出来；从 `limit - 10` 一路试着往上加，试到第一条爆栈的链为止。
- **`best_of` 把 `repeats` 次塞进一次计时**：量到的是总时间，
  任务 4 的趋势就看不出来了；要每次单独计时、取最小值。
- **`preorder_concat` 偷偷写成累加器**：两个版本就变成同一个函数，
  链状上那一列不再呈平方级。这一份保留拼接版是**故意的**：
  它是要看的对象，不是要改的错。
- **硬凑 `print` 后的数字**：判分读的就是那些行，硬凑等于没做。
  改完先自己跑 `py <任务文件>.py` 对一遍，再跑 `py run_tests.py`。

## 判分在读什么

判分不 import 学生代码来判（探针只用来试函数接口），它读的是**任务脚本自己打印的行**：

```text
任务 1   示例树/链状树/平衡树 各自的 前序/中序/后序/层序 四行
         课件四行（逐字）、空树 四种、单点 四种
         计数 01/02/03（三棵树前序的结点个数）
任务 2   「数据 节点数 树高 对称」表头 + 五行、直接问 is_mirror 的三行
任务 3   树高行 平衡/链状 × 三种规模（六行）、链状 爆栈长度、递归再深一层、
         注释 递归上限、三行判断、计数 01/02/03
任务 4   耗时 01/02/03/04 × 三档规模、倍数四行、形状对照两行、链状/平衡 n=2000 两行、
         计数 01/02/03（两版答案一致、拼接与累加器各自的整段倍率）
```

留白版原样跑是不通过的（本机实测 4 个任务 17 PASS / 72 FAIL、退出码 1，没有 Traceback）：
四种遍历都交回 `[]`、表里全是 `0 0 False`、树高全是 0、四类耗时全是 `0.000000`。
那是起点，不是 bug——每条 FAIL 都点出了缺哪一段 TODO。

判分另有几个**探针进程**，它们 import 你的任务文件、拿判分**自己搭的树**去试函数：
任务 1 试空树/单点/判分自己的树/值里带 `0` 的树，还试「传进去的列表有没有被接着用」
（这是累加器版的证据）；任务 2 试 `is_mirror` 的四个分支与两种形状上的树高；
任务 3 在顶层自己二分出那条爆栈线，再看 `max_safe_depth` 交回的值与它对不对得上；
任务 4 试 `build_chain`、`build_balanced`、`best_of` 的调用次数。

判分看趋势不看常数：任务 4 只要求「链状 200→800（四倍长）拼接涨 8 倍以上、
累加器涨 8 倍以内」，以及「链状上的倍数明显大于平衡树」。秒数换台机器就变，别背；
三档里最小那一档最容易被「第一次跑」的噪声抬高，所以判据用的是整段涨幅（线性该是 4 倍）。

## 做完之后用一句话回答

为什么收集结果要用累加器、而且测性能不能只测一种形状？说清「拼接的代价与形状有关、
不只是与 n 有关」，就算这一课练到位了。