LeetCode-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.

Example :

img

1
2
3
Input: root = [1,2,3,4,5,6]
Output: true
Explanation: Every level before the last is full (ie. levels with node-values {1} and {2, 3}), and all nodes in the last level ({4, 5, 6}) are as far left as possible.

Constraints:

  • The number of nodes in the tree is in the range [1, 100].
  • 1 <= Node.val <= 1000

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/*
 * @Description: 958. Check Completeness of a Binary Tree
 * @Author: libk
 * @Github: https://github.com/libk
 */
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
const isCompleteTree = function (root) {
  const queue = [root]
  // flag表示之前是否遇到过空节点
  let flag = false
  while (queue.length) {
    let length = queue.length
    while (length--) {
      const cur = queue.shift()
      if (cur === null) {
        flag = true
      } else {
        if (flag) {
          return false
        }
        queue.push(cur.left)
        queue.push(cur.right)
      }
    }
  }
  return true
}