LeetCode 958. 二叉树的完全性检验

2025-11-07 HGNULB 约 6 分钟

文章信息 14 个分类 5 个标签

分类

LeetCode CodeTop 中等已解决已掌握 20-50 字节跳动美团快手腾讯猿辅导百度京东虾皮

题目描述

✅ 958. 二叉树的完全性检验

题意分析

给定一棵二叉树的根节点，判断它是不是完全二叉树，返回布尔值。

先把定义摆清楚：完全二叉树要求除最后一层外，其余每一层的节点都被填满；并且最后一层的节点全部集中在左侧连续排列，中间不能出现空缺。换句话说，它允许「右下角缺一块」，但不允许「中间挖洞」。

这个定义里藏着两个必须同时满足的条件，缺一不可：一是不能有「中间层没填满就往下长」，二是最后一层不能出现「先空后满」。很多错误解法只顾住了其中一条。

约束方面，题目保证节点数至少为 1，所以不必纠结空树；但节点值毫无意义，判定只和结构有关，因此任何依赖节点值的思路都是跑偏。节点数上限在千级，允许一遍线性扫描。

边界情况有三类要想到：单个根节点是完全二叉树；只有左孩子没有右孩子的树是完全二叉树；只有右孩子没有左孩子则不是，因为最后一层没有靠左。

解法：层序遍历保留空位

核心思路

问题关键：完全二叉树按层序从左到右观察所有节点位置时，非空节点必须形成连续前缀；一旦出现空位，后面不能再出现非空节点。

为什么选择 BFS：BFS 天然按位置顺序扫描。把左右空孩子也作为 null 入队，树中的缺口就不会被跳过，于是完全性直接转化为“第一个 null 之后是否还出现节点”。

状态与不变量：seenNull 表示是否已经进入层序位置的尾部空白区。它变为 true 后，后续合法队列项只能是 null；若遇到非空节点，说明位置不连续。

正确性：完全二叉树的实际节点占据从根开始的连续位置，所以层序序列一定先全是节点、后全是空位。反之，若首个空位后没有节点，所有非空位置构成连续前缀，前面的层必然填满，最后一层也必然靠左，因此树完全。

解题步骤

将根节点入队，初始化 seenNull = false。

弹出 null 时只把 seenNull 置为 true，不要继续加入它的孩子。

弹出非空节点时，若 seenNull 已为真则返回 false；否则把左右孩子无条件入队。

队列耗尽仍未发现“空后有节点”，返回 true。

以 [1,2,3,4,5,null,7] 为例：节点 3 会依次把 null、7 入队；弹出空位后 seenNull 变真，下一项 7 非空，因此返回 false。而 [1,2,3,4,5,6] 从首个空位开始只会再遇到空位，返回 true。

代码实现

class Solution {
    public boolean isCompleteTree(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        boolean seenNull = false;

        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if (node == null) {
                seenNull = true;
                continue;
            }
            if (seenNull) {
                return false;
            }
            queue.offer(node.left);
            queue.offer(node.right);
        }
        return true;
    }
}

func isCompleteTree(root *TreeNode) bool {
    queue := []*TreeNode{root}
    seenNull := false

    for head := 0; head < len(queue); head++ {
        node := queue[head]
        if node == nil {
            seenNull = true
            continue
        }
        if seenNull {
            return false
        }
        queue = append(queue, node.Left, node.Right)
    }
    return true
}

复杂度分析

时间复杂度：$O(n)$。每个非空节点只处理一次，并产生两个孩子位置，总队列项不超过 2n + 1。

空间复杂度：$O(n)$。队列最多保存与一层宽度同阶的节点和空位。

关键点总结

完全性等价于“层序位置中，非空节点形成连续前缀”。

空孩子必须入队，否则 [1,2,3,4,5,null,7] 的缺口会被过滤掉。

seenNull 是全局状态，不能在换层时重置。

Java 的 ArrayDeque 不允许加入 null，本写法应使用 LinkedList。

易错点总结

见到第一个 null 就返回 false：[1,2,3] 也会遇到叶子的空孩子；空位合法，空位后的节点才违规。

给 null 继续加入两个孩子：队列会无限产生空位，无法结束。

只检查“有右孩子必有左孩子”：[1,2,3,4,null,6,7] 局部看似合法，但最后一层中间有缺口。

使用 ArrayDeque 保存空位：调用 offer(null) 会抛异常；要么用 LinkedList，要么改为直接扫描孩子位置。

相似题目

题目	难度	考察点
102. 二叉树的层序遍历	中等	需要按层切分输出，靠队列长度快照划分每一层
103. 二叉树的锯齿形层序遍历	中等	在分层基础上按奇偶层反转结果顺序
107. 二叉树的层序遍历 II	中等	分层结果自底向上输出，头插或最后整体反转
199. 二叉树的右视图	中等	每层只取最后一个节点，考层内位置的识别
429. N 叉树的层序遍历	中等	孩子数量不固定，遍历 children 列表整体入队
513. 找树左下角的值	中等	取最深一层的首个节点，可用先右后左入队一次遍历得到
515. 在每个树行中找最大值	中等	层内做最大值聚合而非收集全部节点
637. 二叉树的层平均值	简单	层内求和取平均，注意用 `double` 防溢出
662. 二叉树最大宽度	中等	同样用堆式编号，但要算层内首尾编号差且需防溢出
1302. 层数最深叶子节点的和	中等	只保留最后一层的和，每层重置累加器
LCR 044. 在每个树行中找最大值	中等	与 515 同解，练层内聚合的另一份题面
LCR 045. 找树左下角的值	中等	与 513 同解，练最深层首节点的定位
LCR 046. 二叉树的右视图	中等	与 199 同解，练层末节点的提取
剑指 Offer 32 - I. 从上到下打印二叉树	中等	不分层，直接输出一维层序序列
剑指 Offer 32 - II. 从上到下打印二叉树 II	简单	分层输出的最基础形态，返回二维数组
剑指 Offer 32 - III. 从上到下打印二叉树 III	中等	之字形输出，可用双端队列免去反转
面试题 04.03. 特定深度节点链表	中等	每层节点串成链表，输出链表头数组