完全二叉树的节点个数
给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。 完全二叉树 的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层（从第 0 层开始），则该层包含 1~ 2h 个节点。
示例 1：
输入：root = [1,2,3,4,5,6] 输出：6 示例 2：
输入：root = [] 输出：0 示例 3：
输入：root = [1] 输出：1
提示：
树中节点的数目范围是[0, 5 * 104] 0 <= Node.val <= 5 * 104 题目数据保证输入的树是 完全二叉树
进阶：遍历树来统计节点是一种时间复杂度为 O(n) 的简单解决方案。你可以设计一个更快的算法吗？
解法
二分查找+位运算
ts
/**
* 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)
* }
* }
*/
const exists = (root: TreeNode, level: number, k: number) => {
// 1. 计算「方向掩码」：二进制只有1个1，位置在level-1位
let bits = 1 << (level - 1);
let node = root; // 从根节点出发
// 2. 循环：从根节点，一步步走到最后一层，bits>0表示还有方向要判断
while (node !== null && bits > 0) {
// 3. 核心位运算：判断当前位是0还是1 → 决定向左/右走
if (!(bits & k)) {
node = node.left; // 二进制位为0 → 向左子节点走
} else {
node = node.right; // 二进制位为1 → 向右子节点走
}
// 4. 掩码右移一位：处理下一个二进制位，相当于去掉当前判断的位
bits >>= 1;
}
// 5. 循环结束：node不为null → 找到该节点，存在；否则不存在
return node !== null;
};
function countNodes(root: TreeNode | null): number {
// 简单的做法就是通过深搜或者广搜直接遍历整颗树进行统计
// 只要知道树深以及最后一层节点个数就能知道结果，不需要完全遍历整颗树
// 如果树深是h，那么最后一层节点个数最多就是2^(h - 1)个
// 也就是说一个一个确定的话时间复杂度就是O(2^(h - 1))
// 因为是按照左边优先排满，所以可以通过二分查找降低查询复杂度
// 边界情况：空树，节点数为0
if (root === null) {
return 0;
}
// ===== 步骤1：计算完全二叉树的最大层数 level =====
let level = 0;
let node = root;
// 一直向左走，能走多远，层数就是多少（完全二叉树特性：左子树一定是满的）
while (node.left !== null) {
level++;
node = node.left;
}
// ===== 步骤2：确定最后一层的节点编号区间 =====
// 你之前问的核心代码！low=2^level high=2^(level+1)-1
let low = 1 << level, high = (1 << (level + 1)) - 1;
// ===== 步骤3：二分查找【最后一个存在的节点编号】 =====
while (low < high) {
// 核心：向上取整的二分法，避免死循环
const mid = Math.floor((high - low + 1) / 2) + low;
// 判断编号mid的节点是否存在
if (exists(root, level, mid)) {
low = mid; // 存在 → 说明答案在[mid, high]，更新左边界
} else {
high = mid - 1; // 不存在 → 说明答案在[low, mid-1]，更新右边界
}
}
// 循环结束时 low===high，这个值就是最后一个存在的节点编号 → 总节点数
return low;
};