完全二叉树是指按层序从1开始编号时，n个结点的编号恰好为1至n且无空缺的二叉树；它不是左右子树高度差≤1的平衡树，正确判定需用bfs层序遍历，一旦出现空节点，后续所有节点必须为空，否则即非完全二叉树。
什么是完全二叉树，以及为什么不能只看高度差
完全二叉树不是“左右子树高度差 ≤ 1”的平衡树，而是按层序编号后，节点编号必须连续——即如果把根节点编号为 1，左孩子为 2、右孩子为 3，以此类推，那么所有 n 个节点的编号必须恰好是 1 到 n，中间不能有空缺。
常见错误是只检查左右子树高度差是否为 0 或 1，这只能判满二叉树或近似平衡，会漏掉像“根→左→左→右”这种编号断层的情况。
- 正确思路：用 BFS 层序遍历，一旦遇到空节点，后续所有节点都必须为空
- 关键判断点：首次遇到
nullptr后，再出现非空节点 → 直接返回false - 注意：空树（
root == nullptr）是完全二叉树
用 BFS 实现校验，避免递归栈溢出和编号越界
递归方式很难自然维护层序编号，且容易因深度过大导致栈溢出；BFS 天然按层序访问，配合队列能直接模拟编号连续性。
示例逻辑（C++）：
bool isCompleteTree(TreeNode* root) {
if (!root) return true;
queue<treenode> q;
q.push(root);
bool seenNull = false;
while (!q.empty()) {
TreeNode* node = q.front(); q.pop();
if (!node) {
seenNull = true;
} else {
if (seenNull) return false; // 非空节点出现在空节点之后
q.push(node->left);
q.push(node->right);
}
}
return true;
}</treenode>
- 不需要手动计算编号，靠“空节点出现后不能再有非空节点”这一性质即可判定
- 每个节点最多入队一次，时间复杂度
O(n)，空间复杂度最坏O(w)（w 是最大层宽） - 不依赖
TreeNode是否带 parent 或 size 字段，通用性强
测试时容易忽略的边界 case
很多实现能过样例但挂在线上，问题常出在边界处理上。
-
root为nullptr→ 应返回true，别直接 return false 或崩溃 - 单节点树（
root存在，左右都为nullptr）→ 是完全二叉树 - 只有左子节点的两层树（根 + 左）→ 是完全二叉树；但根 + 右 → 不是（编号 2 缺失，3 却存在）
- 最后一层节点全靠左，但中间某层提前出现空位（如：第 2 层左空右有）→ 不是完全二叉树，BFS 会在第二个非空节点处捕获
如果必须用编号法，怎么避免整数溢出
有人想用节点实际编号（1, 2, 3…）来校验是否等于节点总数，但编号最大可达 2^depth，depth=32 就超 int；用 unsigned long long 也不保险。
- 真正需要的只是“编号是否连续”，而非编号本身值 → BFS 空节点哨兵法更安全
- 若坚持编号法，可用 pair
存编号，但需确保初始编号传参正确（根为 1），且每次检查 id —— 这反而要先遍历一遍数节点数，多一遍 O(n)，得不偿失 - 编号法在序列化/反序列化场景有用，但单纯校验完全性，BFS 哨兵法更直接、不易错
真正麻烦的是节点指针本身不保证内存布局连续，所以别试图通过地址算编号；老老实实用队列状态机控制流程。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
