时间限制： 0.5 秒

空间限制： 30 MB

题目描述

所谓的有根有序树 $T$，都有唯一的根节点 $r=\text{root}(T)$，且子树按照顺序可以编号为 $\{T_1,T_2,\cdots,T_d\}$，其中子树总数 $d$ 也称作 $r$ 的度数（注：度数的定义以本题为准，指的是自身子节点的个数）。

我们递归定义 $T$ 的先序遍历序列为：$\text{pre}(T)=\{r\}+\text{pre}(T_1)+\text{pre}(T_2)+\cdots \text{pre}(T_d)$。其中 $+$ 为序列的拼接运算（类似于 C++ string 类的重载运算符 + 作为字符串拼接的作用）。类似地，可以定义后序遍历序列为：$\text{post}(T)=\text{post}(T_1)+\text{post}(T_2)+\cdots +\text{post}(T_d)+\{r\}$。

给出一个有根有序树 $T$ 的先序遍历序列 $\text{pre}(T)$，各节点按顺序组成的度数序列 $\text{deg}(T)$，你需要在 $O(n)$ 的时间以及 $O(1)$ 的额外空间复杂度内求出其后序遍历序列 $\text{post}(T)$。具体要求见下方【交互方式】一栏。

交互方式

这是一道函数式交互题，不需要选手考虑输入输出，也不要从标准输入读入数据，或将任何内容输出到标准输出，否则会影响判题。

你提交的代码需要包含头文件 pre2post.h。

你需要实现一个函数 void pre2post(std::stack<int>& pre, std::stack<int>& deg, std::stack<int>& post)。任给一棵有根有序树的先序遍历序列，以及对应的节点度数序列，计算出对应的后序遍历序列。具体描述如下：

• 初始时，先序遍历序列，节点度数分别自顶而下地存放在栈 pre 和 deg 中，post 栈为空。
• 算法终止时，pre 和 deg 都应为空，后续遍历序列则应自底而上存放在 post 栈中。
• 算法运行时间应当线性正比于树的规模，算法过程中任何时刻的空间占用了（含调用栈），相对于初始时的空间占用量不超过 $O(1)$。

以下我们给出一个代码提交实例（不做任何修改即返回，仅作为可以通过编译的示例，不保证能得分）：

#include "pre2post.h"

void pre2post(std::stack<int>& pre, std::stack<int>& deg, std::stack<int>& post)
{
    return;
}

白盒交互库实例

具体请见附加文件区的 interactor.cc 和 pre2post.h。本题直接采用白盒交互库进行评测。

如果你本地的实现代码为 main.cc，则将交互库放在同一目录下，在 Linux 系统中输入以下命令行即可运行：

g++ main.cc interactor.cc -Wall -std=c++20 -o foo -lm -O2 -I/include

在 Windows 下会生成 foo.exe，在 Linux 下会生成 foo，你可以输入 .\foo.exe 或者 ./foo 命令行执行该文件。或者将交互库接口与你实现的函数统一在单代码文件中进行本地调试即可。

判题方式解释

交互库特性如下：

• 输入的 pre 和 deg 因为是直接插入栈中，因此表示的是实际前序遍历和度数表的倒序。
• 输出的 post 是直接弹出并输出，因此表示的是实际后序遍历的倒序。
• 输出之前，我们会检查 pre 和 deg 是否为空，post 规模是否和 pre 的初始规模一致。若不一致，则直接返回 Runtime Error 的评测结果。

10
0 6 7 8 5 1 4 3 2 9
0 0 0 0 3 1 0 0 2 3

9 0 1 5 6 7 8 2 4 3

样例 1 解释

该样例遵循白盒交互库的形式。输入方式解释见上方。

该树的先序遍历序列为 $\text{pre}(T)=\{9,2,3,4,1,5,8,7,6,0\}$，其对应的度数序列，按照上述次序给出各节点的度数为 $\text{deg}(T)=\{3,2,0,0,1,3,0,0,0,0\}$。

可以得到该树的结构如下：

因此后序遍历为 $\text{post}(T)=\{3,4,2,8,7,6,5,1,0,9\}$。

子任务

对于所有数据，保证节点个数 $n\le 10^6$，输入的树各节点关键码互异，一定是有根有序树结构。

本题无数据梯度，需要通过全部数据获得所有分数。

提示 0

请注意本题非同寻常的空间限制，这意味着你无法额外建树并通过递归/迭代的形式直接进行前序或者后序遍历。此外使用递归也无法通过本提交窗口。如果你的思路是递归，请将其调用栈利用实际的栈进行迭代模拟解决。

提示 1

注意到函数当中传入的是 std::stack<int>& 的引用类型，意味着传入的栈均可修改，因此可以将一些临时信息从栈中取出后再暂存，此时能保证相对于初始时的空间占用复杂度为 $O(1)$ 的。

来源

清华 826 考研初试 2024 - 算法大题