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

约 5 分钟
文章信息 16 个分类 3 个标签
分类
LeetCode CodeTop 中等 已解决 已掌握 20-50 腾讯 字节 阿里 美团 京东 百度 快手 虾皮 米哈游 猿辅导
标签
树 广度优先搜索 二叉树

题目描述

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

image-20260928202617085

image-20260928202617086

题意分析

完全二叉树要求：除最后一层外，其余层都填满；最后一层的节点必须从最左侧连续排列，中间不能留空位。不要求每个节点都有两个孩子，也不要求最后一层填满。

按从上到下、每层从左到右的顺序查看节点位置，合法结构中的真实节点应当形成一个连续前缀。第一次遇到缺失的位置之后，就不能再出现任何真实节点；这一条件同时约束同层的靠左排列与更高层必须填满。

解法：层序遍历保留空位

核心思路

[!blue]

使用队列进行层序遍历，但把每个真实节点的左、右孩子都按顺序加入队列，即使孩子为空也保留对应位置。若过滤掉空孩子，后面的节点会被压到前面，无法发现结构中的缺口。

用 seenNull 记录是否已经遇到过空位置。取出空节点时将它设为真，然后继续处理队列；取出真实节点时，如果标记已经为真，说明空位后面仍有节点，立即返回 false。

这既检查当前层，也检查之后的层：一个层中出现缺口后，如果右侧还有节点，最后一层没有靠左填满；如果更深处还有节点，这个有缺口的层就不是最后一层，同样不允许。因此 seenNull 一旦变为真就不再清除，无需每层单独重置。

空节点本身不再生成两个空孩子，否则会无限产生空位置。真实节点则正常加入左右孩子；完整处理后如果始终没有出现“空位后还有节点”，说明所有实际节点都位于连续前缀中，可以返回 true。叶子的空孩子会触发标记，但只要之后都是空位，就不会错误拒绝合法树。

Java 的队列使用允许空元素的 LinkedList；不能直接换成禁止空元素的 ArrayDeque。Go 的指针切片可以保存 nil，用递增下标依次读取即可保留相同的位置顺序。

解题步骤

  1. 将根节点入队，初始化 seenNull = false。
  2. 依次取出队列元素；若为空，将标记设为真，不继续加入它的孩子。
  3. 若为真实节点且标记已为真，立即返回 false。
  4. 否则按先左后右的顺序将两个孩子都入队，包括空孩子。
  5. 队列处理完仍未违反条件时返回 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)$，队列项总量为线性数量；Go 的下标遍历会保留切片中已经处理过的项。

关键点总结

[!green]

  • 保留位置才能发现缺口：空孩子与真实孩子都按左右顺序入队。
  • 标记跨层保持：空位之后，无论同层还是更深层都不能再出现节点。
  • 只扩展真实节点：空位置只参与判定，不再生成孩子，队列才能有限结束。
  • 容器必须支持空元素：本 Java 实现使用 LinkedList 保存这些位置。

易错点总结

[!yellow]

  • 见到空节点就返回失败：合法树的叶子也有空孩子，应当拒绝的是空位之后又出现真实节点。
  • 跳过所有空孩子：会丢失空位信息，无法判断后面的节点是否过于靠右。
  • 只检查有右孩子时必须有左孩子：这种局部条件不足以保证整层连续，还需检查不同父节点之间的空位顺序。
  • 为 null 继续入队孩子：会不断制造新空位，遍历无法结束。
  • 每层重置标记或改用 ArrayDeque：前者会漏掉更高层的缺口，后者不能直接存放 null。

相似题目

题目 难度 关联与区别
662. 二叉树最大宽度 中等 同样用完全二叉树位置理解空隙，原题求最外节点跨度，本题要求层序空位后不再出现真实节点。
补充题 204. 二叉搜索树与完全二叉树的判定 中等 都按层遍历检查完全二叉树的结构；补充题还要验证二叉搜索树的有序约束。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2025/00882429
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！