958.二叉树的完全性检验

链接：958.二叉树的完全性检验
难度：Medium
标签：树、广度优先搜索、二叉树
简介：给定一个二叉树，确定它是否是一个完全二叉树。

题解 1 - typescript

• 编辑时间：2021-07-29
• 执行用时：144ms
• 内存消耗：46.8MB
• 编程语言：typescript
• 解法介绍：dfs 递归遍历。

function isCompleteTree(root: TreeNode | null): boolean {
  if (root === null) return true;
  const n = count(root);
  let m = 1;
  let cnt = 0;
  while (cnt + 2 * m < n) cnt += m <<= 1;
  return judge(root, n, m);
  function count(node: TreeNode | null): number {
    if (node === null) return 0;
    return count(node.left) + count(node.right) + 1;
  }
  function judge(node: TreeNode | null, n: number, m: number): boolean {
    console.log(node, n, m);
    if (node === null) return n === 0;
    if (n === 0) return false;
    if (n === 1) return node.left === null && node.right === null;
    const sum = Math.max(0, m * 2 - 1);
    const left = Math.min(m, n - sum);
    const right = n - sum - left;
    return (
      judge(node.left, ((sum - 1) >> 1) + left, m >> 1) &&
      judge(node.right, ((sum - 1) >> 1) + right, m >> 1)
    );
  }
}