力扣链接：222.完全二叉树的节点个数

难度：⭐

✏️ 方法一：我的掘金文章详细解答

解题关键词：二叉树、二分查找、位运算

解题思路：使用层序遍历的顺序把每个节点从 1 开始往后编号，每个编号变成二进制，除去第一位开始看，就是根节点到每个节点的顺序，0代表向左走，1表示向右走。一开始得到最大层级后，就可以知道最下面一层的编号是多少到多少（第h层（h从0开始）：最小编号是 2的h次方，最大编号是 2的(h+1)次方 - 1），然后使用二分法，逐渐判断每个节点是否存在，用一个 exist 的函数，来判断，实现使用位运算，从二进制编号从第二位开始往后面取，最后看节点是否存在。

WARNING

从第二位往后取的逻辑就是每一层需要的 bits，就是每一层除去第一位，然后需要多少位拿到路径，层数h从0开始计算，第h层需要的 bits = 2的(h-1)次方，然后每判断一位，这个 bits 要右移一次，然后拿到下一位的路径值。

/**
 * 判断一个节点（k）是否存在的函数
 * root：根节点
 * level：最后一层
 * k：节点
 */
const exists = (root, level, k) => {
  // 除去第一位二进制数，然后需要看的位数，第 level 层需要看 2的(level-1)次方的位数
  let bits = 1 << (level - 1);
  let node = root;

  // 当节点不为空，且还没有拿完后面的位数
  while (node !== null && bits > 0) {
    // 判断这一位是0 还是 1
    if (!(bits & k)) {
      // 0就往左走
      node = node.left;
    } else {
      // 1就往右走
      node = node.right;
    }
    // 然后右移一位，去拿下一位
    bits >>= 1;
  }

  // 如果 node 最后不为空，那么这个节点就是存在的
  return node !== null;
}

var countNodes = function (root) {
  if (root === null) {
    return 0;
  }

  // 层数
  let level = 0;
  let node = root;

  // 因为是完全二叉树，所以一直往左走，就是最大层数
  while (node.left !== null) {
    level++;
    node = node.left;
  }

  // 第 level 层编号最小是 2的level次方，最大是2的(level+1)次方 - 1
  let low = 1 << level, high = (1 << (level + 1)) - 1;
  // 使用二分法找到最后一层的最后一个节点
  while (low < high) {
    const mid = Math.floor((high - low + 1) / 2) + low;
    if (exists(root, level, mid)) {
      low = mid;
    } else {
      high = mid - 1;
    }
  }
  return low;
};

✏️ 方法二：

解题关键词：二叉树、递归

解题思路：递归判断一颗树是不是满二叉树，如果是二叉树，直接运用公式返回节点数量，如果不是二叉树，使用递归分别判断左右子树，最后加和。 <br /

function countNodes(root: TreeNode | null): number {
  // 如果当前节点为空，返回0
  if (root === null) return 0;

  // 左右子树
  let left = root.left, right = root.right;
  // 左右子树深度
  let leftDepth = 0, rightDepth = 0;

  // 计算最左边深度
  while (left) {
    leftDepth += 1
    left = left.left
  }
  // 计算最右边深度
  while (right) {
    rightDepth += 1
    right = right.right
  }

  // 如果两边的深度相同，说明是一颗满二叉树，那么直接使用公式
  // 因为当前节点是根节点，也占用一层，所以要 depth + 1
  if (leftDepth === rightDepth) return 2 ** (leftDepth + 1) - 1

  // 不是满二叉树，使用递归分别计算左右子树节点数量，并且加上当前节点的数量
  return 1 + countNodes(root.left) + countNodes(root.right)
};