2023-03-15.md

题目

958. Check Completeness of a Binary Tree

Given the root of a binary tree, determine if it is a complete binary tree.

In a complete binary tree, every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes inclusive at the last level h.

思路

BFS

代码

// runtime % memory %
var isCompleteTree = function(root) {
  const queue = [root]
  let nullFound = false
  while (queue.length) {
    const length = queue.length
    const nodes = queue.splice(0, length)
    for (let i = 0; i < length; i++) {
      if (nodes[i] == null) {
        nullFound = true
        continue
      }
      if (nullFound) return false
      queue.push(nodes[i].left)
      queue.push(nodes[i].right)
    }
  }
  return true
}