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

Categories:

题目描述
思路分析
1. 解法一：层序遍历判空（推荐）
相似题目

题目描述

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

思路分析

解法一：层序遍历判空（推荐）

核心思路：

使用 BFS 层序遍历。

一旦遇到空节点，后续所有节点必须都是空，否则不是完全二叉树。

用标记 seenNull 表示是否已经遇到空节点。

复杂度分析：

时间复杂度：O(n)，其中 n 表示节点数量。

空间复杂度：O(n)，队列存储当前层节点。

import java.util.*;

class Solution {
    public boolean isCompleteTree(TreeNode root) {
        Deque<TreeNode> queue = new ArrayDeque<>();
        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 len(queue) > 0 {
		node := queue[0]
		queue = queue[1:]

		if node == nil {
			seenNull = true
			continue
		}
		if seenNull {
			return false
		}

		queue = append(queue, node.Left)
		queue = append(queue, node.Right)
	}

	return true
}

相似题目

题目	难度	考察点
102. 二叉树的层序遍历	中等	BFS
111. 二叉树的最小深度	简单	BFS
662. 二叉树最大宽度	中等	BFS
958. 二叉树的完全性检验	中等	BFS
222. 完全二叉树的节点个数	中等	树

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/00882429