时间限制： 1.0 秒

空间限制： 512 MB

题目背景

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

struct BinNode
{
    BinNode *lc, *rc;  // 左儿子和右儿子
    int size;          // 以当前节点为根的子树节点个数
}

题目描述

你需要实现实现 rank 函数，传入二叉树的根节点 $T$，以及整数 $k$，你需要找出二叉树中前序遍历第 $k$ 个节点。设二叉树有 $n$ 个节点，我们保证 $1\le k\le n$。

交互方式

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

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

你需要实现一个函数 BinNode* rank(BinNode* T, int k)，传入二叉树的根节点 $T$，以及整数 $k$，返回二叉树前序遍历第 $k$ 个节点。你需要在时间复杂度 $O(h)$ 和空间复杂度 $O(1)$ 的限制下实现上述算法。

以下我们给出一个代码提交实例（固定返回根节点，仅作为可以通过编译的示例，不保证能得分）：

#include "rank.h"
BinNode* rank(BinNode* T, int k)
{
    return T;
}

白盒交互库实例

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

白盒交互库先读入一个整数 $q$ 表示对二叉树进行插入或者查询的总数。此时二叉树只有一个节点编号为 1 的根节点。接下来读入 $q$ 行，表示不同操作：

• $1~f~x$：设此操作之前有 $n$ 个节点，则新建 $n+1$ 号节点，以 $f$ 号节点为父节点。$x=0$ 时 $n+1$ 为 $f$ 的左子节点，$x=1$ 时为右子节点。
• $2~k$：查询此时二叉树前序遍历的第 $k$ 个节点。

对于所有的操作 2，都会输出一行一个正整数，表示查询到的节点编号。

10
1 1 1
1 2 0
1 3 0
1 2 1
1 5 0
2 4
1 3 1
2 4
2 1
2 2

4
4
1
2

子任务

对于所有数据，保证操作次数 $q\le 2\times 10^5$，任何时候二叉树高度不超过 $100$。

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

提示

请好好利用每个节点的 size。

来源

清华 826 考研初试 2019/2020 - 算法大题，补充