二叉树遍历¶

解法与署名¶

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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