时间限制： 1.0 秒

空间限制： 64 MB

题目背景

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

struct BinNode
{
    BinNode *fa;       // 父亲（对于根节点为 NULL）
    BinNode *lc, *rc;  // 左儿子和右儿子
};

题目描述

给定二叉树 $B$，节点接口定义见【题目背景】。

你需要实现以下两个函数：

• std::pair<BinNode *, int> first(BinNode *T)：找到以节点 $T$ 为根的子树的后序遍历的第一个节点，以及第一个节点到 $T$ 的距离。
• std::pair<BinNode *, int> next(BinNode *u)：给定二叉树上节点 $u$，求出该节点在 $B$ 的后序遍历的后继节点，此外求出 $u$ 与后继节点的距离。我们保证传入的节点一定存在后继（在后序遍历中，仅根节点不存在后继）。

其中 std::pair<T1, T2> 是 C++ 当中的一个模板类，它允许你将两个可能不同类型的值存储为一个单元。利用以下方式即可构造一个 std::pair 模板类：

T1 a;
T2 b;
std::pair<T1, T2> c = std::make_pair(a, b);
T1 d = c.first;
T2 e = c.second;

利用 std::make_pair 将两个类型与 std::pair<T1, T2> 中类型相对应的数据即可结合为一个 std::pair 单元。然后通过调用其 first 和 second 成员即可分别得到 pair 中的第一个和第二个元素。

在二叉树当中，定义 $a$ 到 $b$ 的距离为从 $a$ 开始沿父亲节点/左右子节点的方向走到 $b$ 的通路，所经过的二叉树边个数。

交互方式

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

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

你需要实现【题目描述】当中的两个函数。

以下我们给出一个提交代码实例（均返回传入节点以及 0，不保证能得分）：

#include "bintree.h"
std::pair<BinNode *, int> first(BinNode *T)
{
    return std::make_pair(T, 0);
}
std::pair<BinNode *, int> next(BinNode *u)
{
    return std::make_pair(u, 0);
}

白盒交互库实例

具体请见附加文件区的 interactor.cc 和 bintree.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$ 行表示节点 $i$ 的左子节点和右子节点的编号，若为 $0$ 则代表无对应子节点。他们代表了一棵 $n$ 个点，编号为 $1\sim n$ 的二叉树的初始状态，其中保证 $1$ 一定为根。

交互库输出如下：

• 第一行有 $n$ 个整数，为通过先调用 first 再持续调用 next 得到的后序遍历序列；
• 第二行有 $n$ 个整数，第一个数表示根节点到后序遍历第一个节点的距离，后 $n-1$ 个数表示后序遍历序列中 $n-1$ 对互为前驱后继关系的节点的距离（按后序遍历顺序输出）；
• 第三行一个整数，表示第二行 $n$ 段距离的总和。

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

6 8 4 2 5 7 3 1
2 3 1 1 3 2 1 1
14

样例 1 解释

该二叉树的形态如下图所示。

子任务

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

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

提示 1

在实现 next 的时候，也可以有效地复用 first 函数。

提示 2

交互库第三行的输出部分即为原题第三小问的证明题（即证明按照本题白盒交互库的方式进行遍历的复杂度为 $O(n)$）。可以观察一下该结果与输入的 $n$ 有什么关系呢？

至于证明过程，则可以查看邓俊辉《数据结构》教材 5.4.4 迭代版后序遍历的过程示意图分析，以及课件 PPT 中对应章节的“沿藤分解”部分。

来源

清华 826 考研初试 2017 - 算法大题（2）