★ FEATURED ARTICLE 刷题库或者准备机试、面试算法题的时候难免会遇到一类让人第一眼发怵的题目给你一串数字让你构建一棵“完全二叉搜索树”。光听名字就觉得要同时处理两个概念好像既要保证搜索树的有序性又要保证树形结构的完全性很多同学第一反应就是先排序再一个个插入建树结果折腾半天写出来的代码又长又容易错。其实这个题本质上并没有那么复杂——它考的就是完全二叉树的数组存储和二叉搜索树中序遍历的有序性这两件事能不能真正理解到位。只要打通了这两个点代码可以短到十几行而且连指针都不用。这篇内容我会从题目拆解开始把“为什么排序之后按中序遍历位置填进去就得到正确答案”讲透再给出可直接抄作业的完整代码顺便把我自己反复踩过的坑和调试过程都记录下来。不管是准备研究生机试、找工作笔试还是单纯想把这棵树的构建逻辑弄明白都可以参考这篇的思路。如果你是那种看着递归就头疼的选手也不用怕我会尽量把每一步在脑子里发生了什么解释清楚。1. 题目到底在问什么把“完全二叉搜索树”拆成三个关键词很多问题之所以显得难不是解法真的复杂而是题干里叠加了好几个术语。CBST这个缩写看起来唬人拆开就是 Complete Binary Search Tree三个词各管一件事。先逐个搞清楚再组合起来看思路就顺了。1.1 完全二叉树不是“满二叉树”树形结构里有两个容易混的词满二叉树和完全二叉树。满二叉树要求每一层的节点都是满的比如高度为3的满二叉树第一层1个、第二层2个、第三层4个总共7个节点一个不多一个不少。完全二叉树的要求稍微宽松一些除了最后一层上面每一层都必须满最后一层可以不满但节点必须从左到右连续排列中间不能空着。举个例子假设现在有6个节点第1层1个、第2层2个、第3层3个这样第3层只有3个节点且它们都靠左排列这就是一棵完全二叉树。但如果第3层的节点分布是左1个、右2个中间空了一个位置那就不是完全二叉树了。这个“从左到右连续”的约束非常关键因为它让整棵树可以像数组一样顺序存储——每个节点的位置都能用下标的算术关系算出来而不需要额外记录左右孩子指针。很多以数组为基础的树形结构比如堆就依赖这个性质。1.2 二叉搜索树的中序遍历是升序的二叉搜索树BST的定义比较直白对于任意一个节点它的左子树里所有节点的值都小于当前节点右子树里所有节点的值都大于当前节点。这个定义保证了整棵树在“结构”上是有序的但有序性最直观的体现并不是层序遍历而是中序遍历。所谓中序遍历就是按照“先左子树、再根节点、最后右子树”的顺序去访问整棵树。数学上很容易证明对于一棵BST中序遍历的结果恰好是一个严格递增的序列。反过来也一样如果你拿到一个BST的中序遍历序列它一定是有序的。这意味着什么意味着给定一串乱序数字只要把它们从小到大排好序那这个有序序列就能直接当作某棵BST的中序遍历结果来用。这是解开这道题的核心钥匙后文构建方法的所有合理性都建立在这一条性质上。1.3 两个性质叠加为什么这题能成为经典单独看完全二叉树它解决的是“存储结构”问题——可以用连续数组不用指针单独看BST它解决的是“节点取值”问题——中序遍历结果有序。把两者合在一起就出现了一个非常漂亮的巧合如果一棵树既是完全二叉树又是BST那么它的结构完全由节点数量N决定与具体数值无关它的数值排列又完全由中序遍历的有序序列决定。那构建这棵树就等价于回答一个问题给定一棵完全二叉树的“空壳子”把有序序列按什么顺序塞进每个节点的位置答案就是按中序遍历的顺序去塞。因为在完全二叉树里每个节点在数组中的下标对应了它在这棵树里的“位置”而对这棵空壳树做一次中序遍历就得到了一个访问顺序。把排好序的数列从小到大逐个填入这个访问顺序里的每个位置最终得到的每个节点都会满足“左子树都比自己小、右子树都比自己大”——这不就原地构建出一棵CBST了吗这个思路的好处在于整个过程不需要真的去“建”树不需要malloc节点不需要维护左右子树指针只需要一个数组和一次递归填充。我第一次意识到这个解法的时候感觉像发现了一个藏在题目里的捷径代码量少得令人怀疑。2. 为什么用中序遍历填充数组就能构建成功上一节说了结论这节把推导过程完整捋一遍。搞清楚“为什么”之后代码怎么写都是水到渠成的事哪怕忘了细节也能自己推出来。2.1 完全二叉树的数组编号规则要从数组构建完全二叉树首先得确立一个编号规则。最常用的是从1开始编号根节点放在数组下标1的位置那么对于任意下标为i的节点它的左孩子下标是2i右孩子下标是2i1。反过来当前节点的父节点下标是i/2整数除法向下取整。这个规则很容易验证。根节点下标是1左孩子是2、右孩子是3下标2的节点左孩子4、右孩子5下标3的节点左孩子6、右孩子7。画出图来看就是一个从上到下、从左到右逐层编号的过程。只要树是完全的所有节点编号就连续不存在中间跳号的情况因此可以用一个长度为N1的数组严丝合缝地把整棵树存下来。从0开始编号也不是不行只是孩子下标变成2i1和2i2父节点变成(i-1)/2计算稍微绕一点。我个人强烈建议做题时统一用从1开始的方案一来写起来直观二来判断“当前下标是否越界”只需要比较i和n的大小一行搞定。2.2 中序遍历填充的完整推演光说不练没有感觉我拿一个N5的例子完整走一遍。假设题目给的原始序列是42513。第一步先排序得到有序序列12345。这个序列就是要填充进树的所有值。接下来用一个全局指针pos从0开始表示下一个要填入的有序序列元素。然后对“完全二叉树的空壳”做中序遍历。所谓空壳就是一棵已经定好形状、但所有节点都还没有赋值的树这个形状完全由N5决定根节点下标1左子树以2为根右子树以3为根下标2的左孩子是4右孩子是5。中序遍历的访问顺序是先访问根为2的那棵子树再访问根节点1最后访问根为3的那棵子树。子树内部同样递归。一步一步来看访问下标1先进入左子树下标2下标2有左孩子下标4先进入下标4下标4没有孩子作为第一个访问位置填入1pos变成1回到下标2填入2pos变成2进入下标2的右孩子下标5下标5作为第三个访问位置填入3pos变成3下标2的子树访问完毕回到根节点下标1填入4pos变成4最后进入右子树下标3没有孩子填入5最终数组存放的结果是下标14下标22下标35下标41下标53。这个数组对应的完全二叉树的层序遍历就是42513而它的中序遍历结果恰好是12345。你把这棵树画出来会看到它确实满足BST的所有约束。这个推演过程其实就是整个算法的核心理解了它代码里递归的逻辑就只是一行“左、中、右”的事。2.3 反直觉点构建过程中你从来看不见“整棵树”这个解法最初让我不适应的地方在于递归过程中我并没有建立任何显式的节点连接代码跑着跑着树就自己“长”出来了。原因是完全二叉树的结构信息完全隐藏在数组下标的算术关系里递归函数每一次调用传入的index本身就代表着“当前正在访问树中的哪一个位置”。访问完左子树回到当前节点再进入右子树这种顺序恰好就是中序遍历对真实二叉树的访问方式。换句话说我们其实是对“数组抽象出来的树”做中序遍历而不是对“指针连起来的树”做遍历。这两者在逻辑上是等价的只是后者需要你手动创建节点前者不需要。把这一点想明白之后很多类似问题都能打开新思路只要是能用数组存储的完全二叉树结构都可以用这种“对下标递归”的方式操作比如后面会提到的堆、线段树的某些场景。3. 完整代码实现与逐行拆解思路清楚了代码就是翻译。我用C写一个完整版本并逐段说明每个变量的作用。如果你习惯Java或者Python把数组操作换一下语法就行核心递归逻辑完全一致。3.1 递归版核心代码#include bits/stdc.h using namespace std; const int MAXN 1005; int n; int a[MAXN]; // 排序后的中序序列 int tree[MAXN]; // 存储完全二叉树的数组下标从1开始 int pos 0; // 指向a数组中下一个要填入的值 void build(int idx) { if (idx n) return; build(idx * 2); // 先处理左子树 tree[idx] a[pos]; // 再填入当前根节点 build(idx * 2 1); // 最后处理右子树 } int main() { cin n; for (int i 0; i n; i) cin a[i]; sort(a, a n); build(1); for (int i 1; i n; i) { if (i 1) cout ; cout tree[i]; } cout endl; return 0; }核心函数build只有四行但每一行都有讲究。idx表示当前正在访问的节点在完全二叉树数组中的下标。进入函数后首先判断idx是否越界一旦下标大于n说明这个位置没有节点直接返回。build(idx * 2)代表去访问左子树访问完之后有序序列的下一个值就应该填到当前节点上所以执行tree[idx] a[pos]。最后再递归访问右子树。这个“左→赋值→右”的顺序完美复刻了BST中序遍历的定义。3.2 层序遍历为什么直接输出数组就是答案普通二叉树做层序遍历需要借助队列从根节点出发一层一层把节点入队再出队。但完全二叉树就不需要因为它的数组下标本身就已经是层序遍历的顺序了下标1是根下标2、3是第二层下标4、5、6、7是第三层依此类推。所以构建完成之后只要从下标1到n把数组按顺序输出得到的就恰好层序遍历序列中间不用任何额外处理。这也是这个算法省事的第二个地方——不但不需要建树连层序遍历的队列都省了。很多人在这一步卡住是因为惯性思维总觉得“树”必须有指针其实在这个问题里数组就是树树就是数组。3.3 复杂度分析为什么这个方案优于“建树再层序遍历”排序的时间复杂度是O(N log N)递归构建每个节点只访问一次是O(N)最后输出也是O(N)。空间上除了输入数组和树数组只有递归栈的消耗。在完全二叉树中树高大约是log2(N1)所以递归深度很浅完全不用担心爆栈。如果按“先构建真正的二叉树再层序遍历”的老思路做你需要先给每个节点动态分配内存再写插入函数最后还要写队列层序遍历代码量是上面的三四倍时间复杂度最坏还会退化到O(N^2)。两者一对比数组方案在简洁性、时间空间开销上都明显占优。这个差距不是微小的优化而是思想层面上的降维打击。4. 踩坑实录那些让提交卡住的细节代码再短写的时候也有一堆地方容易出错。我自己第一次写这道题时连续栽了好几个跟头后来把这些问题整理出来才发现几乎全是细节意识的问题搞清楚之后就能稳定一遍过。4.1 数组从0开始还是从1开始千万别混这是最经典的一个坑。如果你习惯C语言的数组天然从0开始很容易把根节点放在tree[0]然后递归传build(0)孩子下标变成build(2 * i 1)和build(2 * i 2)。这样写理论上也能对但判断越界、计算父节点时都要修改公式稍不留神就写串。更常见的情况是代码里一会儿用下标1一会儿用下标0结果数组第一个元素总是没有被正确赋值输出的时候出现莫名其妙的0。我的建议是研究清楚一个版本然后用习惯。在这篇文章的代码里数组大小开成n1递归入口传1孩子下标直接用2i和2i1。所有地方统一用从1开始的编号你不信试试代码几乎不会因为下标问题出bug。如果最后输出时你发现第一个数不对先检查是不是把tree[0]当成tree[1]用了。4.2 输出格式行末空格和换行在线评测系统对输出格式的容忍度不同有些系统会忽略行末多余空格有些则不会。保险起见用我在代码里的写法在第一个数之前不输出空格之后每个数前置一个空格。这样输出的行末尾不会有空格格式最干净。很多同学习惯每输出一个值就跟着一个空格最后手动删掉行尾空格其实没必要这么麻烦。用一个if(i 1)判断或者i从1循环到n在i之前打印空格都是更简单的处理方式。换行符也要记得输出尤其是最后一行有些评测机对缺少结尾换行很敏感。4.3 递归深度与重复数据问题完全二叉树的递归深度最多是树高N在几百、几千甚至十万时都很安全因为log2级别的高度怎么都压不爆栈。但如果你的递归函数写得不对比如左右子树调用写反了或者忘了越界判断就可能变成无限递归直接崩掉。调试时如果程序卡死先检查递归终止条件。重复元素是另一个容易纠结的点。题目一般会说输入是互不相同的整数但偶尔也会遇到没说清楚的情况。如果数列里有重复值排序之后序列仍然是非递减的按照中序填充的办法最后得到的树仍然可以满足“左子树小于等于根、右子树大于等于根”的弱化版本。大多数题目的判定逻辑不会因此出错所以不用特别担心。保险起见可以读题时注意一下是否明确说明元素互异。4.4 排序前别忘了读入所有数据还有一个新手常犯的错边读入边排序或者排序写在了读入循环内部导致数据还没读全就开始处理。应该先完整读入n个元素存进数组然后一次性sort。这个错误和题目无关属于基础编码习惯但刷题压力大的时候真的容易犯。建议养成习惯凡是需要排序的题都严格遵循“完整读入→排序→处理”三步走。5. 从这道题迁移出去的三种玩法说实话这道题本身已经覆盖了两个重要的算法基础点但它的价值不止于AC一道题。把这个“数组下标映射树结构 中序遍历填充”的思路记牢你在很多其他地方都会再次遇到它。5.1 变体一要求输出后序遍历怎么办后序遍历的顺序是“左子树→右子树→根节点”。完全二叉树的数组存储规则完全不变只需要把递归函数里的三行代码重新排列一下先build(idx * 2)再build(idx * 2 1)最后执行tree[idx] a[pos]。这样填入的顺序就变成了后序遍历要访问节点的顺序。如果把“中序填坑”理解成一种模板那么无论题目要什么遍历顺序你只需要调整填充动作在递归调用的位置其他代码一行都不用改。这个套路可以自己写几个小数据验证一下理解会非常深刻。5.2 变体二构建普通的二叉搜索树如果是普通BST而不是完全BST数组存储就不适用了因为普通BST的形状随插入顺序变化节点编号是不连续的。这时只能老老实实定义结构体用指针或索引把节点串起来先排序也不一定有用因为插入顺序决定了树的形状。这正好从反面说明了“完全二叉树能用数组存”这个性质有多珍贵。面试时如果被问到“为什么要用数组而不是链表”你可以直接拿这个题目当例子说明在树形完全确定的场景下数组方案更简单、更快、还不容易泄漏内存。5.3 变体三堆和线段树里的同款下标映射堆是另一个典型的完全二叉树它也用数组存储父子节点也用2i和2i1这套下标规则。只是堆关心的是大根小根性质而不是搜索树的有序性所以构建方式从“中序遍历填充”变成了“上浮/下沉调整”。线段树虽然不一定完全但很多实现里也用下标方式组织节点父子关系同样是2倍关系。如果你能把这道题的下标映射彻底吃透再看堆排序和线段树的代码会感觉亲切很多因为它们底层共享了同一套“数组即树”的思想。最后再分享一个实操里的小经验我后来做这类树结构题都会在草稿纸上先画一个N5或N7的完全二叉树标好每个节点的数组下标然后手动模拟一遍中序遍历顺序把所有位置编号写出来。这个习惯帮我省下了大量调试时间——很多bug其实在写代码之前就能从纸上暴露出来。这道1064题虽然只是众多树结构题中的基础款但把它做透后面接触堆、线段树、以及各种遍历顺序调整的变体题都会顺畅得多。如果你在被这道题折磨不妨先停下来把那个“空壳树”画一遍再回头看代码你会有一种“原来它在做什么”的透彻感。
阅读完成 · 觉得有帮助？
