0958. 二叉树的完全性检验【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - BFS
• 3. 🔗 引用

1. 📝 题目描述

• leetcode

给你一棵二叉树的根节点 root，请你判断这棵树是否是一棵 完全二叉树。

在一棵 完全二叉树 中，除了最后一层外，所有层都被完全填满，并且最后一层中的所有节点都尽可能靠左。最后一层（第 h 层）中可以包含 1 到 2^h 个节点。

---

示例 1：

输入：root = [1,2,3,4,5,6]
输出：true
解释：最后一层前的每一层都是满的（即，节点值为 {1} 和 {2,3} 的两层），且最后一层中的所有节点（{4,5,6}）尽可能靠左。

示例 2：

输入：root = [1,2,3,4,5,null,7]
输出：false
解释：值为 7 的节点不满足条件「节点尽可能靠左」。

---

提示：

• 树中节点数目在范围 [1, 100] 内
• 1 <= Node.val <= 1000

2. 🎯 s.1 - BFS

js] <<< ./solutions/1/1.c [c] <<< ./solutions/1/1.py [py

/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isCompleteTree = function (root) {
  const queue = [root]
  let seenNull = false

  while (queue.length) {
    const node = queue.shift()
    if (!node) {
      seenNull = true
    } else {
      if (seenNull) return false
      queue.push(node.left)
      queue.push(node.right)
    }
  }

  return true
}

• 时间复杂度：$O(n)$，其中 n 是树的节点数
• 空间复杂度：$O(n)$，BFS 队列

算法思路：

• BFS 逐层遍历，将每个节点（包括 null）加入队列
• 一旦遇到 null 节点后又遇到非 null 节点，则不是完全二叉树

3. 🔗 引用

• 完全二叉树
  • 百度百科