时间限制： 2.0 秒

空间限制： 2 MB

题目背景

所谓 Fib-AVL 树，就是每一个非叶子节点的右子树高度都比左子树高度大 1 的二叉树。例如下图中为高度 $h=1,2,3$ 的 Fib-AVL 树。在本题中，根节点的深度定义为 $0$。

题目描述

设高度为 $h$ 的 Fib-AVL 的节点总数为 $\eta(h)$。

假定从 $0$ 开始，以层次遍历对 Fib-AVL 的节点依次进行编号，请设计一个算法，求出该树的先序遍历序列，要求时间复杂度为 $O(\eta (h))$，空间复杂度为 $O(h)$。请注意本题非同寻常的空间限制，空间并不能完整地存储该树。

交互方式

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

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

你需要实现一个函数 void preorder(int h)。给定 Fib-AVL 树的高度 $h$，输出其前序遍历序列。

你可以调用以下函数：

void print(int u);

通过 print 函数，输出一个节点的编号。每个节点编号都需要按照顺序输出恰好 1 次。为了正确判题，你需要调用该函数进行输出，而不是直接将节点编号输出到标准输出。

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

#include "fibavl.h"
void preorder(int h)
{
    print(0);
    return;
}

白盒交互库实例

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

交互库会读入 Fib-AVL 树高度 $h$，调用 preorder 输出一行 $\eta(h)$ 个整数，表示其前序遍历序列。

请注意，在本地利用白盒交互库测试时，输出前序遍历序列时并不遵守题目的空间限制，此外在调试时最好将传入参数控制在 $1\le h\le 25$ 的范围进行测试。

1

0 1

2

0 1 2 3

3

0 1 3 2 4 5 6

4

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

样例 4 解释

$h=4$ 的 Fib-AVL 树如图。

5

0 1 3 7 4 8 9 14 2 5 10 11 15 6 12 16 13 17 18 19

样例 5 解释

$h=5$ 的 Fib-AVL 树如图。

子任务

对于所有数据，保证 $1\le h\le 40$。

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

提示

$\eta(40)=433494436$，所以很显然是不可能让你完整地存储树空间啦~我们保证黑盒测试库中的 print 函数不产生额外空间占用，且一定能在规定的时间限制内处理完所有的 print。

请注意本题非同寻常的空间限制，如有需要，请使用 int 类型的静态数组进行存储。此外，引用万能头（bits/stdc++.h）或者使用动态数组 vector 也会消耗大量空间，建议不要使用。

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

来源

清华 826 考研初试 2026 - 算法大题（3）