# 二叉树遍历

## 解法与署名

出题人解法：先序确定当前根，中序位置划分左右子树，依次输出左、右、根。Codex（GPT-6）将递归调用改写为显式任务栈，使百万结点链也可处理；划分原理保持一致。程序：[std.cpp](std.cpp)。

另提供[笛卡尔树方案](solution-alternative-cartesian.zh.md)及[程序](alternative-cartesian.cpp)。该方案将先序排名作为优先级，用单调栈重建树，两者均为线性时间。标程采用直接对应遍历定义的区间划分；笛卡尔树作为另一种建模保留。

## 根与区间

保存每个编号在中序中的位置。当前子树的中序区间为 $[l,r]$ 时，尚未消费的先序遍历的第一个编号就是根 $u$ .设它在中序中的位置为 $p$ ，则左子树对应 $[l,p-1]$ ，右子树对应 $[p+1,r]$ .

由于编号互异，$p$ 唯一。左右子树继续满足同样的性质，唯一确定整棵树。

## 显式任务栈

有两种任务：展开非空中序区间，以及输出一个已确定的根。展开区间时，从先序取出根，把下列任务依次压栈：

1. 输出当前根。
2. 展开右子树，若非空。
3. 展开左子树，若非空。

栈后进先出，所以实际处理顺序是左子树、右子树、根。展开任务仍按先序的根、左、右顺序消费编号；输出任务不消费先序编号。

## 正确性

对区间长度归纳。单结点区间输出该结点，正确。一般区间的根由先序唯一确定，中序把其余元素准确划入两棵子树。归纳假设保证两次子任务分别输出正确后序，之后输出当前根，恰为整棵子树的后序。初始任务覆盖完整中序区间，所以最终输出正确。

## 复杂度与实现

每个结点各有一次展开和一次输出，时间 $O(n)$ .先序数组、中序位置表与任务栈共 $O(n)$ 空间。实际待处理任务数量为 $O(h)$ ，其中 $h$ 为树高；程序预留线性容量，以免扩容，分配空间仍按 $O(n)$ 计。

不使用系统递归栈，也不需要分配左右孩子数组。笛卡尔树方案显式保存孩子关系，适合后续还需要访问树结构的场景，同为 $O(n)$ 时间与空间；具体内存、耗时见实测。

## 验证与运行

从显式生成的小树直接遍历得到三种序列，对拍左右链、交替链、平衡树及随机树；正式输入覆盖百万结点的对应结构及打乱编号。

每题的 `tests/plan.json` 包含十份输入的固定种子和目的。编译程序后，可运行：

```text
python tests/generate.py --out-dir <output-directory> --std <compiled-program>
```

省略 `--std` 只生成输入，`--case 01` 选择单份输入。独立验证脚本见 [check_r15.py](../../../tools/check_r15.py)。五轮交替计时与内存记录见[测量数据](../../../docs/benchmark-R15.json)，环境说明见[评测环境与性能](../../../docs/评测环境与性能.md)。有限测试与具体程序的计时不代替上面的证明，也不保证所有同阶实现都能在同一时限内通过。

## 实测结果

| 程序 | 最慢用例中位时间 | 峰值工作集 |
| --- | ---: | ---: |
| 标程 | 0.200720 秒 | 24.30 MiB |
| 补充程序 | 0.207337 秒 | 28.08 MiB |

参考时限为 0.5 秒。十份已测正式输入上，两份程序结果一致，均在该时限内完成。上述内存是包含进程开销的峰值工作集，时间与内存的最大值可能来自不同输入。