时间限制： 1.0 秒

空间限制： 70 MB

题目背景

对于任意形态的有根有序树，都可以利用“长子-兄弟表示法”将其转化为一棵二叉树。具体规则为：

• 将一个节点的所有子节点按照某种规则排好先后顺序。
• 将排序后的第一个子节点放在新树中，原节点的左子节点位置。
• 其他子节点在新树中，放在原树中前一个子节点的右子节点位置。

在以 $r$ 为根的一般树中，任一节点 $v$ 与 $r$ 之间通路上的所有节点（包含 $r$ 和 $v$ 自身）都称为 $v$ 的祖先。如果节点 $a$ 同时是 $v$ 和 $u$ 的祖先，则称作 $v$ 和 $u$ 的公共祖先。显然，$r$ 是所有节点的公共祖先。在两点公共祖先中深度最大的节点，即为最近公共祖先（Lowest Common Ancestor）。

题目描述

对于有根有序树，定义一个节点的深度为：该节点到根节点的通路所经过的节点个数（包含该节点和根节点）。

对于有根有序树的层次遍历序列，我们定义其不同节点的先后顺序：

• 若两个节点 $x,y$ 的深度不同，则比较两个节点的深度。若 $x$ 的深度更小，则层次遍历序列中 $x$ 在 $y$ 的前面；反之则是 $y$ 在 $x$ 的前面。
• 若两个节点 $x,y$ 的深度相同，则找到他们的最近公共祖先 $z$，以及 $x,y$ 分别到 $z$ 通路上的倒数第二个节点 $a,b$。
  • 不难发现，$a,b$ 均为 $z$ 的子节点
  • 此时比较 $a,b$ 在 $z$ 对子节点定义顺序前后。若 $a$ 靠前，则层次遍历序列中 $x$ 在 $y$ 的前面；反之则是 $y$ 在 $x$ 的前面。

不难发现，经过上述规定，对于任意有根有序树都能得到唯一的层次遍历序列。

现在给定一个有根有序树经过“长子-兄弟表示法”所转化的二叉树形式，请你求出该有根有序树的层次遍历序列。

对于二叉树的节点，我们给出以下接口定义：

struct BinNode
{
    int data; // 关键码
    BinNode *lc, *rc; // 左儿子和右儿子
} a[N];

交互方式

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

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

你需要实现一个函数 void traverse(BinNode* x)，传入参数为一个有根有序树经过“长子-兄弟表示法”所转化的二叉树的根节点指针 $x$，在时间复杂度 $O(n)$ 内，给出该有根有序树的层次遍历序列。保证传入的节点不是空节点。

请注意本题的空间限制，这意味着我们不允许你使用递归的方式进行遍历。

此外，你不能更改二叉树的结构。我们会在输出层次遍历之前判断你是否更改了二叉树结构，若发生了更改，则不输出。

你可以调用函数 print(int v)，输出某个节点的关键码。请注意：

• 不要将关键码直接输出到标准输出，否则会影响判题；
• 我们保证二叉树中所有节点的关键码互异；
• 因此你需要按照有根有序树的层次遍历次序，对各个关键码分别调用一次 print；

以下我们给出一个提交实例（只输出根节点的关键码，仅作为可以通过编译的示例，不保证能得分）。

#include "traverse.h"
void traverse(BinNode* x)
{
    print(x->data);
}

白盒交互库实例

具体请见附加文件区的 interactor.cc 和 traverse.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 命令行执行该文件。或者将交互库接口与你实现的函数统一在单代码文件中进行本地调试即可。

白盒交互库会先读入一个正整数 $n$ 表示有根有序树的节点个数。接下来读入 $n$ 行，每行两个整数，分别表示转化的二叉树当中， $i$ 号节点的左子节点和右子节点的编号。特殊地，若其左/右子节点不存在，则对应位置为 $0$。

在白盒交互库中，$i$ 号节点的关键码为 $i$（从而天然地保证了二叉树各节点关键码互异）。

白盒交互库会根据你调用 print 的关键码以及它们顺序进行输出。当与预期的层次遍历序列一致时视为正确。

6
2 0
0 3
4 6
0 5
0 0
0 0

1 2 3 6 4 5

样例 1 解释

原始的树和转化的二叉树结构如下图：

6
2 0
3 0
4 0
5 0
6 0
0 0

1 2 3 4 5 6

样例 2 解释

原始的树和转化的二叉树结构如下图：

6
2 0
3 0
4 0
5 0
0 6
0 0

1 2 3 4 5 6

样例 3 解释

原始的树和转化的二叉树结构如下图：

6
2 0
3 0
4 0
5 6
0 0
0 0

1 2 3 4 6 5

样例 4 解释

原始的树和转化的二叉树结构如下图：

子任务

对于所有数据，保证 $n\le 10^6$，二叉树上所有关键码互异。

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

来源

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