958.二叉树的完全性检验

二叉树的完全性检验

给定一个二叉树，判断它是否是一个完全二叉树。

完全二叉树：除最后一层外，每一层都已填满，且最后一层的节点都尽可能靠左。

示例 1:

输入：[1,2,3,4,5,6]
输出：true

示例 2:

输入：[1,2,3,4,5,null,7]
输出：false

提示:

• 树中节点数在 1 到 100 之间
• -100 <= node.val <= 100

解析

使用 BFS 层序遍历，遇到空节点后不应该再有非空节点。

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)，空间复杂度 O(N)。