时间限制： 1.0 秒

空间限制： 512 MB

题目背景

给定以下二叉树的节点接口定义：

struct BinNode
{
    BinNode *fa;       // 父亲（对于根节点为 NULL）
    BinNode *lc, *rc;  // 左儿子和右儿子
    int size;          // 以当前节点为根的子树节点个数
};

需要注意的是，在本题中你只能访问上述成员，但不可直接修改上述成员。具体我们将在【交互方式】中给出说明。

此外，在本题当中你可以直接使用前三个小问的函数。

题目描述

你需要实现 BinNode *splay_to_comp(BinNode *rt) 函数，通过伸展至任意真祖先的操作，将一棵一般的二叉树调整为完全二叉树，并返回该完全二叉树的根。要求总时间复杂度不超过 $O(n\log n)$，递归深度不超过 $O(\log n)$。

交互方式

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

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

在本题中你无法直接访问并修改二叉树节点的各成员，因此我们提供以下函数：

BinNode *get_fa(BinNode *);
BinNode *get_lc(BinNode *);
BinNode *get_rc(BinNode *);
int get_size(BinNode *);

调用对应函数，即可获取传入节点对应成员的具体值。当传入 nullptr 时，则返回默认值（指针均为 nullptr，整数为 0）。

你可以调用 int lSize(int) 函数，传入完全二叉树的节点规模，返回该二叉树的左子树接节点规模。

你可以调用 BinNode *rank(BinNode *T, int k)，传入二叉树的根节点 $T$，以及整数 $k$，返回二叉树中序遍历第 $k$ 个节点。若 $T$ 的节点规模为 $n$，则必须保证传入的 $k$ 满足 $1\le k\le n$。

你可以调用 void splay_to(BinNode *a, BinNode *x) 函数，传输参数为节点 $a$ 和非空节点 $x$，必须保证 $a$ 为 $x$ 的真祖先，或者为 NULL（空节点）。该函数提供了和伸展树完全相同的伸展操作，但是是将 $x$ 节点伸展至 $a$ 节点的子节点位置。我们保证在伸展操作结束后，所有父子关系的节点都将父节点/左右子节点指针指向了正确位置，无需选手手动调整。

• 当 $a$ 为 $x$ 的真祖先时，伸展操作结束后 $a$ 为 $x$ 的父节点。由于伸展操作只使用到左旋和右旋这两个等价变换，因而不会修改原始二叉树的中序遍历序列。因此若中序遍历序列中 $x$ 在 $a$ 前面，则伸展操作结束后 $x$ 为 $a$ 的左子节点，否则 $x$ 为 $a$ 的右子节点。
• 当 $a$ 为 NULL 时，则与伸展树的伸展操作完全相同，将 $x$ 伸展到树根的位置。

以下我们给出一个代码提交实例（不做任何操作并返回传入的根节点，仅作为可以通过编译的示例，不保证能得分）。

#include "splay.h"
BinNode *splay_to_comp(BinNode *rt)
{
    return rt;
}

白盒交互库实例

具体见附加文件区的 interactor.cc 和 splay.h。需要注意的是，该白盒交互库并非实际评测使用的交互库。

此外，上述提供可用的函数在白盒交互库中均未给出具体实现。如果需要在本题利用白盒交互库进行调试，请参照以下题目完成上述内容：

• lSize：完全二叉树的左子树规模
• rank：二叉树中序遍历第 k 个节点
• splay_to：伸展树 - 伸展至任意真祖先（Splay to）

你可以将实现的函数放在 interactor.cc 中并进行本地测试。

但是黑盒交互库中已经实现好了这几个函数，因此如果想提交的话，无需实现上述函数直接提交即可。

如果你本地的实现代码为 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$ 行表示节点 $i$ 的左子节点和右子节点的编号，若为 $0$ 则代表无对应子节点。他们代表了一棵 $n$ 个点，编号为 $1\sim n$ 的二叉树的初始状态，其中保证 $1$ 一定为根。

白盒交互库会输出一行字符串：

• Not a complete tree!：表示最终形态并非完全二叉树。
• OK!：表示最终得到了正确的完全二叉树形态。

需要注意的是，黑盒交互库不会采用这种方式，直接输出 OK! 并结束程序不会得分。

8
2 3
6 4
5 7
0 8
0 0
0 0
0 0
0 0

OK!

样例 1 解释

其中一种具体的解法如下，从上到下 4 次调用 splay_to 即可将其转为完全二叉树。其中除了第 2 次调用之外，其余调用没有对二叉树进行实际的变换。

子任务

对于所有数据，保证 $n\le 6\times 10^5$。

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

提示

可以注意一下本题以及上述题目链接的“来源”一栏，看看这几道题之间是否有什么关联呢？

此外，白盒交互库当中判断二叉树是否为完全二叉树的代码也可以学习一下，也可以参考 leetcode 958. 二叉树的完全性检验 一题。

如果想不明白怎么一口气实现的话，可以尝试一下递归实现本题。

来源

清华 826 考研初试 2020 - 算法大题（4）