Lstmxx的空间

958. 二叉树的完全性检验

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

百度百科中对完全二叉树的定义如下：

若设二叉树的深度为 h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。（注：第 h 层可能包含 1~ 2h 个节点。）

链接

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function isCompleteTree(root: TreeNode | null): boolean {
  if (root === null) return false
  const nodeQue: TreeNode[] = [root]
  let depth = 0
  while(nodeQue.length) {
    const nodes = nodeQue.splice(0)
    const len = nodes.length
    let isFindNull = false
    let isFindNumAfterNull = false
    depth++
    for(let i = 0; i < len; i++) {
      const node = nodes[i]
      if (node.left === null) {
        isFindNull = true
      } else {
        if (isFindNull) {
          isFindNumAfterNull = true
          break
        }
        nodeQue.push(node.left)
      }
      if (node.right === null) {
        isFindNull = true
      } else {
        if (isFindNull) {
          isFindNumAfterNull = true
          break
        }
        nodeQue.push(node.right)
      }
    }
    if (
      isFindNumAfterNull ||
      (nodeQue.length > 0 && len !== 2 ** (depth - 1))
    ) return false
  }
  return true
};