判断完全二叉树：层序遍历一遍

本文属于「408 算法拓展训练」——考纲内、真题代码题尚未考过的经典题。判断完全二叉树是「层序遍历」这一考点的代表题，也是理解层序遍历如何顺带做结构判定的好例子。它是经典训练题，不是真题，也不押题。

题目

给定一棵二叉树，判断它是否为完全二叉树：除最后一层外，其余各层结点数都达到最大值，且最后一层的结点从左到右连续排列、中间不能有空缺。例如层序为 1 2 3 4 5 6 的树是完全二叉树；层序为 1 2 3 4 _ _ 6（2 号结点缺右孩子，但 3 号结点有右孩子 6）不是，因为最后一层出现了「前面空、后面又有」的空缺。设计算法判断给定二叉树是否为完全二叉树。

这道题没有「尽可能高效」的要求。按拓展训练导语的分类，它属于「直观即满分」型——层序遍历一遍，顺带判定，就是这道题要求的全部。

直观解法：层序遍历,把空孩子也入队

完全二叉树的定义本质是「按层序展开后不能有中间空缺」。层序遍历天然是按「一层一层、从左到右」的顺序访问结点，只要在遍历时连空指针也当成普通元素一起入队，就能把「空缺出现的位置」暴露出来：一旦队列里弹出过一个空结点，说明这棵树在这个位置之后已经"断"了，如果后面还能弹出非空结点，就是空缺、就不是完全二叉树。

#include <stdbool.h>
#include <stddef.h>

typedef struct TreeNode {
    int data;
    struct TreeNode *left, *right;
} TreeNode;

bool isComplete(TreeNode *root) {
    if (root == NULL) return true;              // 空树视为完全二叉树

    TreeNode *queue[10000];                       // 数组模拟队列
    int front = 0, rear = 0;
    bool seenNull = false;                         // 是否已经弹出过空结点

    queue[rear++] = root;
    while (front < rear) {
        TreeNode *node = queue[front++];
        if (node == NULL) {
            seenNull = true;                       // 记录:从这里开始不能再有非空结点
        } else {
            if (seenNull) return false;            // 空结点之后又出现非空,空缺,不完全
            queue[rear++] = node->left;             // 空孩子也照常入队
            queue[rear++] = node->right;
        }
    }
    return true;                                    // 全部弹完都没违反规则
}

拿层序 1 2 3 4 _ _ 6（2 号结点缺右孩子，3 号结点有右孩子 6）走一遍：依次弹出 1、2、3，把它们的孩子（含空）入队；弹到 2 的右孩子时是空，seenNull 置真；继续弹，轮到 3 的左孩子（空）、3 的右孩子 6——6 非空，但此时 seenNull 已经是真，立即返回 false，正确识别出「2 号右孩子空了、3 号右孩子却非空」这处空缺。

复杂度：层序遍历访问树上每个结点（以及它们的空指针位置）一次，时间 $O (n)$ ；队列最多同时容纳一层的结点，空间 $O (n)$ （最坏情况，比如满二叉树的最后一层）。

为什么它就是满分解

这道题没有「暴力 vs 最优」的分差。用总纲的「找浪费三问」审一遍，三问全部答「没有」：

有没有重复扫描？ 没有。每个结点（含空指针位置）只入队、出队一次，判定逻辑在它被弹出的那一刻就完成，不需要之后回头再看。
有没有重算已知的东西？ 没有。seenNull 这个布尔标记一旦置真就不会撤销，后续的判定直接复用它，不需要每次都重新扫一遍已经出队的部分。
有没有放着性质不用？ 没有。层序遍历「一层一层、从左到右」的顺序，正好是完全二叉树定义里「空缺是否连续出现在末尾」这条性质需要的访问顺序，不需要额外信息。

更根本的一条：判断是否完全二叉树，至少要把树上每个结点看一遍（少看一个，就可能漏判某处空缺）——遍历一遍就是 $O (n)$ 的下界，任何正确算法都躲不开。碰到下界，直观写法即最优。

真正的难点在「空后不能再非空」这条判定

分不在优化上，在把这条核心规则写准：

空孩子必须照常入队，不能跳过。如果写成「孩子非空才入队」，队列里就永远不会出现空结点，seenNull 也永远不会被置真——整个判定逻辑直接失效，任何树都会被判成完全二叉树。把空指针当成普通元素一起入队，是这道题和普通层序遍历最大的区别，也是最容易被下意识省略的一步。
判定的时机是"弹出"而不是"入队"。要在从队列里弹出一个结点时检查 seenNull，而不是入队时——因为空结点也要正常入队（好让它在稍后被弹出、触发 seenNull 置真），但它本身不需要再展开孩子。
seenNull 一旦置真就不能重置。它是一个只能从假变真、不能再变回假的标记，代表"从这个位置往后，树已经断了"。如果在某个分支里误把它清空重置，会让后面真正的空缺被放过。

三处任何一处出错，代码依然「跑得动」，但会把有空缺的树误判成完全二叉树（或者反过来），且不会有任何崩溃提示——这正是这类判定题最隐蔽的失分方式。

层序遍历判定,看一遍

用层序 1 2 3 4 _ _ 6（2 号结点缺右孩子，3 号结点却有右孩子 6）演示——注意队列弹出 2 的右孩子（空）之后，seenNull 置真，紧接着弹出 3 的右孩子 6（非空）时立即判定为不完全：

加载可视化中...

演示为 JavaScript 版本，逻辑与上文 C 代码一一对应（可自行把 3 号结点的右孩子去掉，换成层序完整无缺的树，观察结果变为 true）。

别画蛇添足

这道题结构简单，过度设计的空间不大，但有两个常见的「想复杂了」：

先算出结点总数和树高,再套公式验证。完全二叉树的结点数和树高之间确实存在数量关系（比如 $2^{h - 1} \leq n \leq 2^{h} - 1$ ），但这只是一个必要条件，光验证数量对不上结构，无法排除"数量对但位置错"的情形（比如空缺出现在中间某处、被别处的多余结点补齐了总数）。层序遍历直接检查"空后是否再非空"，一步到位，不需要绕这个数量关系。
递归判断每个子树是否满或者是否只在最后一层缺。完全二叉树的递归定义写起来要分好几种情况讨论（左右子树高度是否相等、缺口在左边还是右边），比层序遍历的一条规则复杂得多，也更容易漏掉某个分支。层序遍历把"结构是否连续"这件事转化成了"队列里空结点后面还有没有非空结点"这一条简单判定，没必要用递归重新发明一遍。

下一步

看层序遍历判断完全二叉树的交互演示：层序遍历可视化
回到方法论源头：「暴力解到最优解」真题专题总纲

判断完全二叉树：层序遍历一遍 ​

题目 ​

直观解法：层序遍历,把空孩子也入队 ​

为什么它就是满分解 ​

真正的难点在「空后不能再非空」这条判定 ​

层序遍历判定,看一遍 ​

别画蛇添足 ​

下一步 ​