讲真如果让我在数据结构入门题里挑一道“看起来在考你写建树代码、实际上考你有没有想通遍历序”的代表1064 Complete Binary Search Tree一定排前三。题面很简单给你一串互不相同的整数要求构造一棵既是完全二叉树、又是二叉搜索树的树最后按层序遍历输出。第一次做这道题的人很容易陷入一个误区——把 BST 插入函数抄出来然后开始旋转调整代码越写越长逻辑越补越乱。实际上这道题真正的解法是“不建树”先用数组把完全二叉树的位置固定下来再用中序遍历的顺序把排好序的键值一个个填进对应位置最后数组从左到右一读就是层序答案。这篇文章就把这个“中序遍历构建完整搜索二叉树”的思路彻底拆开从原理推导、手推样例到避坑经验一次讲清适合正在刷题、被这题卡住的读者。1. 拿到题先别写代码CBST 到底由哪两条规则拼成1.1 题目到底让你做什么输入第一行是节点个数 n第二行是 n 个互不相同的整数键值。要求建立一棵“完全二叉搜索树”再输出它的层序遍历。注意关键词完全二叉搜索树英文是 Complete Binary Search Tree简称 CBST。它不能拆开理解成“随便建一棵 BST再想办法变完全”而是同一个结构必须同时满足下面两条规则规则一完全二叉树。除最后一层外每一层节点都要填满最后一层虽然允许不满但节点必须从左到右连续排列不能有空洞。用数组编号表达就是根节点编号 1任意编号为 i 的节点左孩子编号 2i右孩子编号 2i1这个编号规则从 1 开始且连续到 n。规则二二叉搜索树。任意节点的左子树里所有键值都小于它右子树里所有键值都大于它。对 BST 做中序遍历拿到的序列一定是严格递增的有序序列。这两个条件叠加之后会有一个非常反直觉的推论对于固定数量的键值集合CBST 的形态是唯一的。完全二叉树每一层的空位数量、最后一层从哪里开始连续排布只由 n 决定跟键值本身没有任何关系。也就是说你手里其实不是“一棵待构建的树”而是一个“已经画好格子、只差往格子里填数字”的模板。1.2 同时满足两个性质不是嘴上说说那么简单如果你已经知道 BST 的中序序列是有序的可能第一反应是那我先做一次中序遍历把排好序的值放回树里不就行了这个方向非常接近正确答案但需要更精确地落地因为“放回树里”的前提是树的结构已经存在。普通 BST 的模板是动态长出来的没有一个预先定死的空位体系CBST 的模板则是完全二叉树空位体系从第 1 个节点到第 n 个节点全部确定。完全二叉树的“严格”体现在哪举一个直观例子n6 和 n7 的树长得不一样。n7 时三层全满n6 时前两层全满最后一层只有两个节点而且必须挂在左边编号 4 和 5 位置编号 6、7 的位置是空的。这个“只能挂在左边”的约束直接导致如果你能把中序遍历的下标序列算出来那么所有空位怎么分配值都有了唯一答案。1.3 这道题真正考的是“规律”不是“数据结构模板”我见过很多人做这题第一件事就是把 AVL 或者红黑树的插入旋转代码翻出来试图在插入过程中维护完全二叉树结构。这不是不行但工作量完全失控完全二叉树要求的“最后一层之前全满、最后一层从左到右连续”是比 AVL 的“高度差不超过 1”更硬的结构约束要设计一套旋转规则去动态维护它复杂度远超出普通平衡树题目的范围。所以这道题的题眼不是“怎么写一个会平衡的 BST”而是“识别出结构已经被完全二叉树定死然后利用中序序列的有序性去做分配”。想通这一点代码量会骤减到几十行想不通你会在一堆旋转函数里耗尽时间。2. 为什么“逐个插入”这条路我劝你别走2.1 插入顺序决定形状而你要的形状是定死的普通 BST 的构建是逐点插入从根开始比当前节点小往左走大往右走直到找到空位。这个方法的问题在于最终形态完全由插入顺序决定。同样的键值集合按不同顺序插进去可能得到一棵漂亮的平衡树也可能得到一条链表。CBST 要求的是确定形状而不是“任意一种满足 BST 性质的形状”。这就意味着逐点插入后你还需要大规模调整树的结构才能把它变成完全二叉树的形状。举个例子n7 时如果我把排好序的 1 到 7 依次插入得到的就是一棵只有右子树的链状树和完全二叉树差着十万八千里。有人可能想那我按层序顺序构造节点再往里面填值这个思路已经接近正解但还缺最关键的一步——你要知道每个位置上应该填什么值而这正是中序遍历才能告诉你的。2.2 旋转调整有多繁琐从 AVL 到 CBST 不是换壳AVL 树靠左旋、右旋维持每个子树的高度平衡但它从来没保证过“最后一层之前全满”。CBST 比 AVL 的结构要求更苛刻所以想沿用旋转思路的人会遇到一连串问题单旋转会把某一层挤歪双旋转也未必能把最后一层的节点全部挤到左边连续排列。你需要重新设计判断条件、重新推导旋转触发时机、处理各种边界子树……这已经不是“一道题”的复杂度而是“半个平衡树课题”的工作量。而且别忘了旋转过程中还要保持 BST 的中序有序性等于在结构变换的同时维护数值分布双线作战。对刷题来说这是完全没必要的痛苦。2.3 反常识点位置顺序只由 n 决定和值无关真正让这道题变简单的是一个很多人忽略的观察给定 n完全二叉树的每个数组下标在整个中序遍历里排第几个是预先确定的常数序列。与键值大小完全无关。于是问题被劈成两半第一半对 1 到 n 的数组下标做一次中序遍历得到固定下标序列比如 n7 时是 4、2、5、1、6、3、7第二半把键值排序后按这个下标序列依次填入数组。第一半解决“位置分配”的几何问题第二半解决“值的有序性”的搜索树问题。两半拼起来CBST 直接生成。这也是“中序遍历构建完整搜索二叉树”这个标题的核心含义不主动构造树而是让中序序列当向导把值带到它该去的位置。3. 中序填值的完整推导从数组到有序键值3.1 完全二叉树的数组存储规则完全二叉树天生适合用数组存这也是层序遍历输出那么容易的原因。约定数组下标从 1 开始tree[1] 是根tree[i] 的左孩子是 tree[2i]右孩子是 tree[2i1]父节点是 tree[i/2] 向下取整。下标从 1 开始很关键因为编号和完全二叉树的层序编号完全一致最后从左往右打印数组就是一层一层往外读。这个结构同时保证了数组中每个下标恰好对应唯一一个节点位置任意节点到根的路径完全由下标二进制决定。比如下标 5二进制是 101去掉首位01 代表“左、右”严格说路径是1 是根第二位 0 表示从根到左孩子下标2第三位 1 表示再往右孩子走下标 2*215。这种下标即路径的性质就是后续中序遍历能直接作用在数组上的原因。3.2 数组下标的中序遍历序列那条固定的分配顺序既然数组本身就是一棵完全二叉树的“躯壳”那就完全可以对数组下标做中序遍历。递归逻辑不访问“键值”而是访问“位置号”先递归处理当前位置的左孩子下标再“访问”当前下标最后递归处理右孩子下标。因为每个位置的孩子下标是固定的所以最终得到一个只随 n 变化的下标顺序。手动推 n7 的顺序根下标 1左子树根下标 2一直往左下走到下标 4下标 4 没有左右孩子于是第一个被访问的下标就是 4。回退到下标 2第二个访问下标 2再进右孩子下标 5第三个访问下标 5。回退到下标 1第四个访问下标 1然后进右子树下标 3往左下到下标 6第五个访问下标 6回退下标 3第六个访问下标 3最后访问右孩子下标 7。整个顺序写出来就是4 → 2 → 5 → 1 → 6 → 3 → 7这个序列的下标居中位置是 1左边全是下标 1 的左子树右边全是下标 1 的右子树非常漂亮。3.3 为什么“按序填入”能同时满足两个性质现在把键值升序排列。比如键值是 1 到 7排好后就是 [1, 2, 3, 4, 5, 6, 7]。我按 4→2→5→1→6→3→7 的顺序依次取值填入得到数组下标填入键值41225314653677检查 BST 性质根节点是下标 1值 4。左子树是下标 2 的 2、4、5对应值 1、2、3全都小于 4右子树是下标 3、6、7对应值 5、6、7全都大于 4。继续往下看下标 2 的值 2它的左孩子下标 4 是 1右孩子下标 5 是 3右侧刚好都小于 2 或大于 2。整棵树全部满足 BST 的中序递增特性。为什么必然成立因为中序遍历访问顺序本身就是“左子树全部节点 → 根 → 右子树全部节点”而键值又是升序数组。先被分配到一个节点左子树的那些值永远是整体上小于这个节点值的那些数同理被分配到右子树的永远是更大的数。递归到每一层相同逻辑继续生效于是 BST 性质从根到叶子逐层“自动成立”。同时我们只是把值填进数组数组的下标关系没有变过所以完全二叉树结构从头到尾都成立。3.4 直接层序输出数组就是答案这是整道题最爽的地方不需要 BFS不需要层序遍历函数。层序遍历的定义就是“根、第二层从左到右、第三层从左到右……”而数组下标 1 到 n 的顺序恰好就是这个顺序。构建完成后直接 for 循环打印 tree[1] 到 tree[n] 即可。用上面 n7 的例子直观验证数组顺序是 4, 2, 6, 1, 3, 5, 7对应根 4、第二层 2 和 6、第三层 1、3、5、7。树的形态和值分布完全符合 CBST 定义。4. 可以参考的实现C 和 Python 各来一版4.1 C 版思路直观、适合踩点核心代码就一个递归函数它不构建任何指针结构只负责把排序后的键值填进数组。#include cstdio #include algorithm using namespace std; const int MAXN 1010; int n; int keys[MAXN]; // 排序后的键值 int tree[MAXN]; // 完全二叉树的数组下标从 1 开始 int fillIdx 0; // 当前取到 keys 的第几个元素 void inorderFill(int pos) { if (pos n) return; // 超出节点范围直接返回 inorderFill(pos * 2); // 先填左子树 tree[pos] keys[fillIdx]; // 再把当前位置填上排好序的下一个值 inorderFill(pos * 2 1); // 最后填右子树 } int main() { scanf(%d, n); for (int i 0; i n; i) { scanf(%d, keys[i]); } sort(keys, keys n); // 升序 inorderFill(1); for (int i 1; i n; i) { if (i 1) printf( ); printf(%d, tree[i]); } printf(\n); return 0; }这里最需要注意递归参数 pos 是数组下标不是键值赋值的等号左边是 tree[pos]右边是 keys[fillIdx]。如果你把这两者搞混输出会一团乱麻。fillIdx 初始为 0每次填完一个节点就递增后续递归自然按顺序消费排好序的键值不需要手动维护任何“当前区间边界”。4.2 Python 版递归更简洁但小心闭包变量import sys def main(): data list(map(int, sys.stdin.read().split())) if not data: return n data[0] keys data[1:1 n] keys.sort() tree [0] * (n 1) # 1-basedtree[0] 不用 idx 0 def inorder(pos): nonlocal idx if pos n: return inorder(pos * 2) tree[pos] keys[idx] idx 1 inorder(pos * 2 1) inorder(1) print( .join(map(str, tree[1:]))) if __name__ __main__: main()用sys.stdin.read().split()的好处是无论输入换行格式怎样都能稳定读取尤其适合键值可能分成多行的情况。nonlocal idx是 Python 递归写法里容易漏掉的点如果漏写赋值会创建一个局部变量导致程序报错或者填错位置。4.3 实测样例与输出验证用几个典型输入跑一遍样例一7 6 3 1 2 5 4 7排序后是 1 到 7输出4 2 6 1 3 5 7样例二5 7 6 5 4 3排序后是 3、4、5、6、7。n5 时中序遍历下标顺序是 4、2、5、1、3所以填充后数组为 6、4、7、3、5输出6 4 7 3 5这个结果可以自己画图验证根节点 6左子树根 4左子树根的左右孩子 3 和 5右子树根 7完全二叉且满足搜索树性质。样例三1 100输出100单节点时递归只填 tree[1]直接输出。4.4 复杂度排序是唯一的大头整个算法有两部分开销排序是 O(n log n)递归填充是 O(n)。空间上tree 和 keys 各自 O(n)递归栈深度等于完全二叉树高度即 O(log n)远小于 n。总体来看这不是一个高复杂度算法代码量和时间都控制得很好。如果键值范围本身已知且可桶排排序部分还可以继续优化但用标准 sort 已经足够。值得一提的是递归栈只有 log n 层不像普通链表式 BST 可能退化成 n 层所以不用担心栈溢出问题。5. 我在实测里踩过的坑和排错思路5.1 下标从 0 开始最隐蔽的翻车点我最早做这道题的时候直接把数组开成vectorint tree(n)然后从inorder(0)开始递归。结果发现下标 0 的左孩子是2*0 0、右孩子是 1完全把下标规律搞乱了。用 0-based 也能写代价是必须把所有公式改成2*pos1和2*pos2而且数组编号和完全二叉树的层序编号对不上最后输出层序的时候你得再处理一遍偏移非常容易错。我的建议是老老实实把数组开成 n1下标从 1 用起。这样既符合完全二叉树的层序编号也让代码和题解更统一查错时能把每一个下标直接对应到纸上画的树节点。5.2 递归里把“位置参数”和“值参数”搞混第二个雷区是把tree[pos] keys[fillIdx]写成了tree[fillIdx] keys[pos]之类的变体。这类错误非常隐蔽因为程序不报错但输出结果完全不符合预期而且很难一眼看出问题。定位这种错误有个技巧在递归里临时打印pos和fillIdx的值对比 n7 的理论过程。正常情况是 pos 按 4、2、5、1、6、3、7 访问同时 fillIdx 从 0 到 6 同步递增。如果发现某个节点 pos 和 fillIdx 不匹配那基本就是赋值语句写反了。5.3 输出格式的细节最后一个数字后面不能有空格刷题最容易因为格式被扣冤枉分。打印层序时如果你直接for循环每位后面跟一个空格最后一个数字后面也有空格评测通常判为格式错误也就是 PE。稳妥写法是第一个数字前不输出分隔从第二个起先输出一个空格再输出数字。单元素特判同样容易忽略但它其实不需要特殊分支上面的写法天然处理i1 时不输出空格直接打印 tree[1]循环结束。5.4 常见 WA 的情况对照表我自己总结了一张快速自查表遇到 Wrong Answer 的时候按表筛查效率很高错误现象可能原因正确做法输出值乱序、不成搜索树没排序就开始填充先sort升序数组开头多个 0tree 开了 0-based 或下标偏移错开 n11-based递归越界或段错误递归边界写成pos n用pos n判断返回输出末尾多空格循环无脑打印tree[i] 先数字后空格数值全对但顺序完全反过来排序降序确认是升序后再填充5.5 一个高效的案头验证法代码写完别急着提交先用 n7、键值为 1 到 7 的样例跑一下这是最标准的“自检模板”。如果输出是 4 2 6 1 3 5 7基本可以放心。再试一个乱序键值比如 6 3 1 2 5 4 7输出应该和前者完全一致因为 CBST 只取决于键值集合不取决于输入顺序。如果两个输出的键值分配不同说明你的排序或填充逻辑有问题。6. 从 1064 看一类“遍历序固定结构”的通用方法6.1 别再把它当孤题提炼成思维模型做完这道题你会发现它背后其实是一个可以复用的思维模型当数据结构的“形”已经确定时不需要反复插入调整只需要确定“某个遍历序”和“键值序”之间的对应关系然后做一次填充。完全二叉树是“形确定”的极端例子数组下标直接把每个位置钉死排序后的键值是“值序确定”的序列中序遍历恰好把位置序列和值序一一对应。这个模型的通用性比想象中大“堆”的构建也依赖完全二叉树数组只是它不用中序而用“下沉/上浮”来维护堆序前序中序重建二叉树本质也是从遍历序列反推结构“序列化与反序列化”同理都是在结构约束下恢复数据。6.2 还能怎么扩展如果把完全二叉树的“左子 2i、右子 2i1”推广到完全 k 叉树那么左子变成 ki 或 ki1中序遍历的计算方式变了但“先定结构、再填有序值”的套路不变。如果键值允许重复BST 的定义需要修士是左小右大、遇相等放左边还是右边不同题目约定不同需要额外处理。另一个有趣方向是如果不要求完全二叉树只要求“给定中序序列你能填出一棵合法 BST”那结果会任意发散因为普通 BST 形状可变。对比之下你更能体会 CBST 的“确定性”——也正是这个确定性让题目从“构造”降维成了“填空”。最后留一个我个人觉得特别有用的动作拿到这类树的题先在草稿纸上把 n7 的树画出来然后把中序遍历的下标写出来再对照代码走一遍。这个操作看着简单但它能让你从“背代码”变成“理解代码”下次遇到 n8、n15都不用重新推直接心里就有数。排序、递归、打印三步走完你会发现所谓的 Complete Binary Search Tree其实是一道披着树壳子的“数组映射题”。