很多人第一次看到“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三层前两层节点数是 3last 6 - 3 3。左子树最底层最多能放 2^(3-2) 2 个节点last 3 2所以左子树是满二叉树节点数 2^(h-1) - 1 3。手动验证一下6 个节点的完全二叉树根的左孩子是节点 2节点 2 又有孩子 4 和 5所以左子树恰好 3 个节点没错。再看 n 4h 3前两层节点数 3last 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) { queueNode* 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 的 1099Build A Binary Search Tree和 1151LCA 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 1h 1last 1 - (2^0 - 1) 1接着计算capacity 1 (h - 2)就会变成1 -1这在 C 里是未定义行为。虽然某些编译器碰巧能算出结果但这是严重的隐患。写位运算时一定要警惕移位负数的情况宁愿多写一个 if也别拿未定义行为赌。类似的边界还有 n 2。此时 h 2last 1capacity 1 0 1last capacity成立左子树是满的节点数 1。验证一下2 个节点的完全二叉树根是 1左孩子是 2左子树只有一个节点正确。6.3 用队列层序遍历时判空别靠数组长度3.3 代码的层序遍历部分用的是queueNode* 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”只需要点一下就能切换界面视角但解题的切换视角得靠脑子里的那根弦时刻绷着。