很多人第一次看到“Complete Binary Search Tree”这个题目时，大概率会像我一样愣一下。BST（二叉搜索树）我熟，完全二叉树我也熟，但这俩拼在一起，还要按层序遍历输出，总觉得哪里卡住了。最关键的是，我刷题时旁边的侧边栏还开着，题目列表晃来晃去，思路也跟着飘。后来我干脆点了下“Toggle Sidebar”把侧边栏收起来，界面清爽了，脑袋也清醒了——这题的突破口恰恰就是一个“切换视角”的动作：在二叉搜索树的中序序列和完全二叉树的数组编号之间来回切换。这篇就顺着这个思路，把题目“1064 Complete Binary Search Tree”的两种主流解法、推导过程和踩坑记录完整写一遍，给之后刷到同类题的人省点时间。
1. 题目在拷问什么：单一约束都会，叠加起来就乱
1.1 两条性质的“单点描述”
先回到题目本身。给你一个长度为 N 的、可能无序的序列，要求构造一棵树，满足两个条件：
- 它是二叉搜索树（BST）：任意节点的左子树所有值小于根，右子树所有值大于根。这里按常见题目约定，左右子树允许相等或严格小于的细节要看题面，PAT 1064 这类题通常互不相同且严格有序；
- 它是完全二叉树：除最后一层外每层节点都是满的，最后一层的节点从左到右连续排布，中间不留空位。
单独看第一条，最粗暴的思路就是排序。BST 的中序遍历结果一定是递增序列，反过来，给一个递增序列，我可以任意选一个根，左边全塞左子树、右边全塞右子树，都能构造出一棵 BST。单独看第二条，完全二叉树的形态本质上是“按编号紧密排列”，和数值大小没关系。问题就出在这里：两个条件分别都有无数种构造方式，一旦叠加，如何确定哪个位置放哪个数？
1.2 常见的错误直觉：先建 BST 再调成完全二叉树
我见过不少人拿到题目之后的第一反应是：先按 BST 插入规则把序列建成一棵二叉搜索树，然后再想办法把这棵树“压扁”成完全二叉树的结构。这个方向基本走不通。BST 的插入结果完全取决于插入顺序，同样的序列，不同的输入顺序会生成形状天差地别的树。你没有办法在事后通过旋转之类的操作，既保持 BST 性质，又保证所有层都是满的、最后一层靠左排列。完全二叉树的形态是“全局紧密”的，它要求某一层的节点数必须先满足上一层全部填满，再谈下一层的排布，这种全局性的约束不是局部旋转能搞定的。
还有一部分人走到了另一个极端：先把序列排好序，放在数组里，然后试图按照某种“层序中位数”的逻辑去猜测每个节点应该填什么值。比如拿中间值当根，左边的一半给左子树，右边的一半给右子树，再递归处理。这个思路方向是对的，坎贝尔（也就是经典的“递归分治建完全 BST”）确实可行，但它有个隐藏的麻烦：完全二叉树的左右子树规模并不总是五五分，到底左子树应该分到几个节点，需要精确计算。我在后面第 3 节会专门展开这一步，很多人就是在这个地方翻车的。
1.3 题目的真正考点：两种结构之间的映射
其实这题的核心是一个“映射”问题。二叉搜索树有一个很好的性质：中序遍历序列 = 递增序列。完全二叉树有一个很好的性质：层序遍历顺序 = 数组下标递增顺序。那么问题就变成了：给定一棵完全二叉树的“骨架”（每个位置长什么样固定），我只要按中序遍历去访问这些骨架上的空位，依次填入递增序列里的值，填完以后，数组下标顺序就是层序遍历结果。
换句话说，我们不需要去“构建”树，我们只需要模拟一棵完全二叉树的中序遍历过程，把排序后的序列按访问顺序填进对应编号的位置里。这个思路一出来，代码量能压缩到 20 行以内。后面我会给出完整实现和推导，但建议你先自己动手写一版，卡住了再回来看。
2. 中序填充法：用数组下标同时表达结构和顺序
2.1 完全二叉树的数组编号规则
要用数组表达完全二叉树，得先统一编号约定。最常见的做法是根节点下标为 1，节点 i 的左孩子下标为 2 * i，右孩子下标为 2 * i + 1。这种编号方式的巧妙之处在于：只要 N 确定，所有节点的下标区间就固定死了，树长什么样完全由编号规模决定，不需要存指针。
举个例子，N = 5 的一棵完全二叉树，节点下标分布是这样的：
- 下标 1：根节点；
- 下标 2、3：第二层；
- 下标 4、5：第三层从左数前两个位置。
因为完全二叉树要求“最后一层从左到右连续”，所以 N = 5 时第三层只可能出现下标 4 和 5，不可能出现下标 6 存在而下标 4 不存在的情况。这个“连续性”是后面一切推导的基础。
如果你习惯从 0 开始编号，那就变成：根为 0，左孩子 2 * i + 1，右孩子 2 * i + 2。两种约定都能用，建议选一种并坚持到底，因为混着用极易在边界判断时出错。我自己的习惯是用 1 开头，因为这样判断“节点是否存在”只需要判断下标是否小于等于 N，语义更直观。下面的代码也都以 1 开头。
2.2 核心思想：中序序列与下标序列的缝合
有了数组编号之后，我们来想一个问题：对一棵用数组存的完全二叉树做中序遍历，访问顺序是什么？中序遍历的顺序是“左子树 -> 根 -> 右子树”，放到数组下标上看就是递归式：
先递归访问 2 * i 位置，再访问 i 位置，最后递归访问 2 * i + 1 位置这个访问顺序和节点存的值没有任何关系。于是我们可以先把输入的 N 个数排好序，让它们成为一个递增序列，接着在中序遍历的过程中，每走到一个“空位”，就从递增序列里按顺序取一个值填进去。为什么这样填完一定满足 BST 性质？因为 BST 的中序遍历结果就是递增序列，而我填入的序列本身就是递增的，中序遍历访问顺序也是确定的“左根右”，两者一对应，每个节点的“左小右大”关系自然成立。
反过来看，为什么填完一定是完全二叉树？因为数组下标对应的就是完全二叉树的物理结构，我从来没有改变过下标的位置关系，只是往这些位置里填值。
2.3 中序填充法的完整代码
下面是基于这个思路的 C++ 实现，这段代码也可以非常轻松地翻译成 Java、Python 或 Go：
#include <bits/stdc++.h> using namespace std; const int MAXN = 1005; int n, idx = 1; int a[MAXN], tree[MAXN]; // 对完全二叉树下标为 root 的节点进行中序遍历 // 实际上是在走“骨架”，边走边填入递增序列的值 void inorder(int root) { if (root > n) return; // 下标越界，说明该孩子不存在 inorder(root * 2); // 左子树 tree[root] = a[idx++]; // 填入当前最小（或说下一个）的值 inorder(root * 2 + 1); // 右子树 } int main() { scanf("%d", &n); for (int i = 1; i <= n; i++) scanf("%d", &a[i]); sort(a + 1, a + n + 1); // BST 中序有序，排序后才能按序填充 inorder(1); for (int i = 1; i <= n; i++) { if (i > 1) printf(" "); printf("%d", tree[i]); } printf("\n"); return 0; }这里用的递归写法比较直白。你可以手动模拟一遍 N = 5 的情况：先递归到下标 4，因为没有左孩子，所以第一个填入的是下标 4 的位置，也就是 a[1]（最小值）；然后回溯填下标 2，再进到下标 5……最终 tree 数组里存的就是层序结果。这个过程就是“用中序遍历来给完全二叉树的空位填空”，核心代码只有几行。
2.4 为什么数组顺序恰好等于层序遍历顺序
这是很多初学者最容易问的问题：为什么最后直接按下标输出 tree[1] 到 tree[n] 就是层序？
因为我们对完全二叉树的数组编号方式，本来就是按层从左到右编号的。下标从 1 到 n 的递增顺序，天然对应着树的层序遍历顺序。这就像你用顺序表存储一棵完全二叉树时，遍历数组本身就是层序遍历。这不是巧合，而是完全二叉树定义和数组编号约定共同作用的结果。
这也意味着，如果你需要输出层序，根本不需要写队列做 BFS，直接打印数组即可。类似的，如果题目要求输出前序、中序或后序，你再按对应顺序去递归访问 tree 数组就行。
3. 递归建树法：当你需要一棵真实指针树时怎么算分治规模
3.1 为什么有时候不能只用中序填充法
中序填充法虽然代码短，但它默认了一个前提：你最终要的输出结果和“数组下标”有关，或者你只需要层序序列。可现实中有不少场景，要求你输出前序遍历、后序遍历，或者后续需要对这棵树做更多操作（比如插入、删除、查询），这时候只有数组就不太够了。更直接地说，如果你在面试里被问到这题，面试官很可能要求你“真正构造出那棵树的结构”，而不是直接给一个数组。
这时候需要换一种思路：既然树的形态固定为完全二叉树，那我从递增序列里找到哪个值作为根，然后递归构建左右子树即可。关键问题是：左子树分几个节点、右子树分几个节点。
3.2 左右子树规模不是简单的“一半一半”
很多人的第一反应是：左子树应该分 floor((n-1)/2)，右子树分 ceil((n-1)/2)。这是错的。完全二叉树虽然整体形状规整，但左右子树的节点数并不是简单对半分，它取决于最后一层的节点具体落在左侧还是右侧。
我们从“外壳”来想：假设当前这棵完全二叉树有 n 个节点，层数记为 h（只包含根节点时 h = 1）。那么前 h - 1 层构成一棵完整的满二叉树，节点数是 2^(h-1) - 1。最后一层节点数 last = n - (2^(h-1) - 1)。这 last 个节点是从左往右依次排在最后一层的，而最后一层在物理上被分成了两个区域：属于左子树的部分和属于右子树的部分。
因为完全二叉树的最后一层是连续填的，所以当 last 的数量足够多，会先填满左子树的最底层，再填右子树的最底层。左子树的最底层最多能放 2^(h-2) 个节点。于是：
- 如果 last >= 2^(h-2)，说明左子树最底层被填满了，此时左子树是一棵高度为 h - 1 的满二叉树，节点数 = 2^(h-1) - 1；
- 如果 last < 2^(h-2)，说明左子树最底层没填满，最后一层的 last 个节点全部属于左子树，此时左子树节点数 = (高度为 h - 2 的满二叉树节点数) + last = (2^(h-2) - 1) + last。
这个公式可能读起来有点绕，我画个场景你就明白了。假设 n = 6，可以算出 h = 3（三层），前两层节点数是 3，last = 6 - 3 = 3。左子树最底层最多能放 2^(3-2) = 2 个节点，last = 3 >= 2，所以左子树是满二叉树，节点数 = 2^(h-1) - 1 = 3。手动验证一下：6 个节点的完全二叉树，根的左孩子是节点 2，节点 2 又有孩子 4 和 5，所以左子树恰好 3 个节点，没错。
再看 n = 4，h = 3，前两层节点数 3，last = 1。last < 2，所以左子树节点数 = (2^(h-2) - 1) + last = 1 + 1 = 2。手动验证：节点 2 有左孩子 4，没有右孩子，所以左子树是节点 2 和节点 4，共 2 个节点，正确。
3.3 递归建树完整代码
有了左子树规模之后，递归逻辑就清晰了：递增序列的中间位置 a[l + leftSize] 是当前子树的根，左侧区间 [l, l + leftSize - 1] 构建左子树，右侧区间 [l + leftSize + 1, r] 构建右子树。
#include <bits/stdc++.h> using namespace std; struct Node { int val; Node *left, *right; Node(int v) : val(v), left(nullptr), right(nullptr) {} }; int a[1005]; // 计算有 n 个节点的完全二叉树的左子树节点数 int getLeftSize(int n) { if (n == 1) return 0; // h = 最大的层数，即 log2(n) 向下取整再加 1 int h = 0; int tmp = n; while (tmp > 0) { h++; tmp >>= 1; } int last = n - ((1 << (h - 1)) - 1); // 最后一层节点数 int capacity = 1 << (h - 2); // 左子树底层最多能容纳的节点数 if (last >= capacity) { return (1 << (h - 1)) - 1; // 左子树是满二叉树 } else { return (1 << (h - 2)) - 1 + last; // 左子树底层未满 } } // 用有序数组 a[l..r] 构建完全BST，返回根节点 Node* build(int l, int r) { if (l > r) return nullptr; int n = r - l + 1; int leftSize = getLeftSize(n); Node* root = new Node(a[l + leftSize]); root->left = build(l, l + leftSize - 1); root->right = build(l + leftSize + 1, r); return root; } void levelOrder(Node* root, int n) { queue<Node*> q; q.push(root); bool first = true; while (!q.empty()) { Node* cur = q.front(); q.pop(); if (!first) printf(" "); first = false; printf("%d", cur->val); if (cur->left) q.push(cur->left); if (cur->right) q.push(cur->right); } printf("\n"); } int main() { int n; scanf("%d", &n); for (int i = 1; i <= n; i++) scanf("%d", &a[i]); sort(a + 1, a + n + 1); Node* root = build(1, n); levelOrder(root, n); return 0; }这段代码里有一个地方值得强调：getLeftSize函数的 h 计算。我直接用了一个 while 循环数 n 的二进制位数，这其实就是 floor(log2(n)) + 1。比如 n = 6，二进制是 110，三位，所以 h = 3，正确。这种方式避免了浮点误差，也避免了需要引入<cmath>。
3.4 两种解法在“输出层序”这个问题上的对比
对于这道题本身（只要求输出层序），中序填充法明显更简短，甚至不需要显式建树。但递归建树法的代码结构更通用。你可以把build函数返回的Node*随意拿去做前序、中序、后序、层序、镜像、寻找公共祖先等等后续操作。两种方法没有绝对的好坏，取决于你是在做 OJ 上的固定题目，还是在做更偏工程/面试的题目。下面这个表给出它们的直观对比：
| 对比维度 | 中序填充法 | 递归建树法 |
|---|---|---|
| 代码量 | 很短，约 20 行 | 较长，约 60 行 |
| 空间占用 | 两个数组即可 | 需要指针节点和队列 |
| 能否前序/后序输出 | 需要额外递归访问数组 | 直接操作树节点 |
| 复杂度 | O(NlogN)（排序主导） | O(NlogN)（排序主导） |
| 思路难度 | 巧妙但依赖“数组即层序”的约定 | 需要理解左子树规模推导 |
| 适用场景 | PAT 等固定输出层序的题目 | 面试、后续需要操作树的场景 |
其实你仔细看会发现，递归建树法里的getLeftSize并不好记，我第一次写的时候推了半天公式，还在last >= capacity这个边界上纠结了很久。后来我研究出一个更“笨”但也更不容易错的替代方案：既然完全二叉树的形状只跟 n 有关，那我可以用中序填充法先把层序数组算出来，再递归地把数组还原成一棵真实树。具体做法是：用层序数组直接构造一棵完全二叉树的骨架，然后对骨架做中序遍历，从层序数组里取值填入对应位置。这种做法本质上就是第 2 节思路的指针版，只是把“数组下标”变成“节点指针”。虽然多了一道转换，但不需要背左子树规模的公式，适合临场忘公式的时候救急。
4. 边界条件和低级但致命的细节
4.1 编号从 0 开始还是从 1 开始
从 1 开始编号时，判断左孩子是否存在用2 * i <= n，右孩子用2 * i + 1 <= n。从 0 开始编号时，判断左孩子用2 * i + 1 <= n - 1，右孩子用2 * i + 2 <= n - 1。两种都行，但很多人写着写着就混了：递归传根节点时用inorder(1)，判断边界却下意识写2 * i + 1；或者反过来。我的建议是，在自己的模板里固定一个约定，并且只用一个。
4.2 递归建树法计算 h 时别用浮点对数
我在 3.3 的代码里用 while 循环数二进制位，这是有意设计的。如果你写成int h = log2(n) + 1;，浮点数的精度问题在某些边界值上会导致 h 算错，比如 n 恰好是 2 的整数次幂时，log2 可能返回一个非常接近但不等于整数的浮点数，再强转成 int 就错了。直接用位运算和循环是最稳的，也顺带避免了一些 OJ 上因为cmath版本不同导致的神奇错误。
4.3 递归深度会不会爆栈
中序填充法的递归深度等于树高，完全二叉树的高度是 O(logN)，所以只要 N 不超过几十万，默认的递归栈都扛得住。递归建树法同理，每次递归规模减半，高度对数级，也不用担心爆栈。真正需要注意的反而是某些极端情况下把递归写成“链状”，但那已经不在这道题的讨论范围里了。
4.4 输入序列有重复值怎么办
严格意义上，PAT 1064 这类题默认互不相同。但如果题目没说明，或者你在力扣上遇到允许重复的变体，这里有个小坑：BST 的定义有“左小右大”和“左小右大且右大不含等”等不同变体。有的题要求左子树小于等于根、右子树大于根，有的则要求左子树小于根、右子树大于等于根，两个定义下的树形可能不一样。不过只要题目最终只要求“满足 BST 性质”且没有额外约束，排序后按中序填充的做法仍然成立，因为相等的值在中序序列里是相邻的，填进相邻位置不会破坏中序有序性。至于真实树的结构，不同定义会给出不同的合法解，OJ 判题时通常只验证性质，不会强制唯一形态。
4.5 输出格式的坑
层序输出看起来简单，但格式问题经常让人白白浪费一次提交。比如要求每个数字用空格隔开、行末不能有空格。我在 3.3 的代码里用了一个first布尔变量，在打印前判断，这个技巧比“先打印全部，再退格删掉末尾空格”要干净得多。类似的，有的输出要求每个数占一行，有的要求换行符统一为\n，提交前一定看清题面。
5. 从“1064”到一类题：复合结构问题的通解思路
5.1 先给每种性质找到最合适的“载体”
刷题刷多了会发现，很多题目看起来复杂，本质上是把两个独立的知识点强行拼在一起，然后问你如何调和。遇到这种题，不要慌，先给每个性质找一个“载体”：
- BST 的载体是中序序列，因为它天然有序；
- 完全二叉树的载体是数组下标，因为它的形状可以完全由下标表达；
- AVL 树的载体是“平衡因子”；
- 堆的载体也是完全二叉树数组，但值的大小关系不同。
题目一旦把两个性质叠加，你要做的就是在两个载体之间建立映射。1064 的经典解法，本质上是“BST 中序序列”到“完全二叉树数组下标”的映射。想清楚这个，你就不只是会做这一道题，而是会做整整一类题。
5.2 类似的题目有哪些
我在刷题过程中碰到过不少和 1064 同源的题目，这里列几个可以作为扩展练习：
- 给定层序序列，判断它是否是一棵二叉搜索树的层序序列；
- 给定一棵完全二叉树的数组存储，输出它的前序或后序遍历；
- 要求把一棵普通 BST 调整成完全 BST（或者反过来验证）；
- 堆排序里经典的建堆过程，本质也是在完全二叉树数组上做下沉调整，和这题的“充分利用数组结构”思路非常接近；
- 力扣上类似“将有序数组转换为平衡二叉搜索树”的题目，则用的是“每次取中点”的分治策略，和本节的递归建树法在形式上很像，但平衡条件和完全条件不同。
做完 1064 之后，我建议你用同样的思路去解一下 PAT 的 1099（Build A Binary Search Tree）和 1151（LCA in a Binary Tree）。1099 是给出一棵树的固定形状，要求填成 BST，思路和中序填充法几乎一样；1151 则进一步考察 BST 的 LCA 性质。这几题连着刷完，“中序有序”这个关键词你会记得非常牢。
5.3 左子树规模公式的“速记”方式
我在 3.2 里给出的公式，可能在很多人看来还是不够直观。这里分享一个我自己记忆的方式：不用记公式，而是用二分的感觉。
当前这棵完全二叉树有 n 个节点，根节点去掉后还剩 k = n - 1 个节点分给左右两棵子树。左子树是一棵完全二叉树，右子树也是一棵完全二叉树，但右子树的深度不超过左子树，且右子树只有在左子树最底层填满的情况下才会出现节点。换句话说，右子树的形态完全由“左子树是否满”决定。所以我只需要判断“最后一层的节点数”是否超过左子树底层容量。这个“容量”就是 2^(h-2)。一旦判断出左子树是满的，直接用满二叉树公式算；如果不满，最后一层所有节点都在左边，左边节点数就是“上一层的完整部分 + 最后一层的节点数”。
如果你实在不想记这个推导，那就在考场上多做一步：用 n 从 1 到 10 手动枚举左子树节点数，观察规律。这个过程本身只需要 30 秒，但能帮你快速校准公式到底对不对。
6. 实测过程中的几条经验总结
6.1 先排序再中序填充，代码虽然短，但思路证明很重要
我记得第一次把这题的 AC 代码发给朋友看时，对方的反应是“就这么点？”确实，中序填充法短到不像一道考察树的题。但如果你不理解“为什么中序遍历访问到的位置恰好应该填入递增序列里的下一个值”，你就无法在题目变体里举一反三。比如，如果把题目改成“给定一棵完全二叉树每个节点上已有的值，要求判断它是不是 BST”，你还是可以用中序序列判断：做一次中序遍历，看看输出序列是否递增即可。
6.2 递归建树法里最容易写错的是左子树规模的返回条件
我在 3.3 的代码中，getLeftSize的第一步就判断了if (n == 1) return 0;。这是必须的。因为如果 n = 1，h = 1，last = 1 - (2^0 - 1) = 1，接着计算capacity = 1 << (h - 2)就会变成1 << -1，这在 C++ 里是未定义行为。虽然某些编译器碰巧能算出结果，但这是严重的隐患。写位运算时一定要警惕移位负数的情况，宁愿多写一个 if，也别拿未定义行为赌。
类似的边界还有 n = 2。此时 h = 2，last = 1，capacity = 1 << 0 = 1，last >= capacity成立，左子树是满的，节点数 = 1。验证一下：2 个节点的完全二叉树，根是 1，左孩子是 2，左子树只有一个节点，正确。
6.3 用队列层序遍历时，判空别靠数组长度
3.3 代码的层序遍历部分用的是queue<Node*> q，很多人会写成“只 push 前 n 个节点”，但因为build已经按需构造出真实的左右孩子，直接用cur->left和cur->right判空即可。如果你把节点指针和一个“已经输出几个数”的计数器混用，容易在完全二叉树的最后一个节点上多输出一个空指针，然后段错误。
6.4 时间复杂度的朴素判断方法
很多读者看到这题会下意识以为建树和层序遍历会带来额外的时间复杂度，其实不会。无论中序填充法还是递归建树法，主要耗时都在sort上，也就是 O(NlogN)。建树的递归过程每个节点只访问一次，是 O(N)。空间复杂度的额外开销也在 O(N) 级别。如果 N 是 10 的 5 次方量级，完全不用担心超时。
6.5 不用 STL 的替代处理方式
我们前面的代码为了简洁用了 STL 的queue和sort。如果你在的是一个禁用 STL 的竞赛环境，也可以用数组模拟队列，或者直接按题目要求的输出方式做递归遍历。中序填充法本身就不依赖队列，层序直接打印数组即可，这种特性在一些环境受限的笔试里非常吃香。我在校招笔试时经常优先考虑“不依赖 STL 且代码量短”的解法，不是为了炫技，而是为了减少出错点。
6.6 从数组反推树的隐藏知识点
最后说一个很多人忽视的细节：给定 n 和一棵完全二叉树的数组表示，你是可以唯一确定树的层序遍历结果的，因为完全二叉树的结构完全由 n 决定，和值无关。这也是为什么这题能做到“输入一串数字，输出一串数字”，而不用像普通二叉树那样通过前序加中序去还原。理解这一点之后，你会发现很多关于完全二叉树的问题，本质上都是数字下标问题。比如求某个节点的父节点，直接i / 2；求某个节点的深度，直接floor(log2(i)) + 1。这些看似零散的小技巧，在做树相关的综合分析题时非常有用。
说实话，这道题我第一次做的时候，栽在了数组开小上——tree[MAXN]我一开始开的是 1000，结果题目 N 上限是 1000，但数组编号到 2 * N 的却不一定访问到，中序填充法实际访问的下标最大就是 N，所以不需要开 2N 那么大。不过递归建树法的指针节点数只有 N 个，也不存在开 2N 的问题。真正需要开 2N 的场景是用数组模拟“按堆结构建树”的时候，树节点编号可能到达 2N。这个细节容易混淆，写代码前想清楚自己用的是什么存储模式，能省下很多莫名其妙的越界报错。
如果你是想在面试里展示自己的代码能力，我更推荐直接说递归建树法，因为它是从“序列区间划分”的角度去构造树，面试官可以从你判断左子树规模的推导中看出你对完全二叉树的底层理解。而如果只是为了刷题拿 AC，中序填充法的代码量优势无可替代。两种方法都值得亲手写一遍，毕竟“Toggle Sidebar”只需要点一下就能切换界面视角，但解题的切换视角，得靠脑子里的那根弦时刻绷着。
