LeetCode 222. 完全二叉树的节点个数：两种解法详解（BFS + 二分查找优化）

LeetCode 中一道非常经典的二叉树题目——222. 完全二叉树的节点个数，这道题看似简单（求节点总数），但如果能结合「完全二叉树」的特性做优化，能极大提升效率，非常适合用来巩固二叉树的遍历和二分查找的结合运用。

先帮大家快速回顾题目，避免踩坑：

一、题目解读

题目给出一棵完全二叉树的根节点 root，要求求出这棵树的节点总个数。

关键是理解「完全二叉树」的定义（划重点，优化的核心就在这）：

• 除了最底层节点可能没填满，其余每层的节点数都达到最大值（也就是满二叉树的层数节点数）；

• 最底层的节点全部集中在该层最左边的若干位置，不会出现“左边空、右边有节点”的情况；

• 若最底层为第 h 层（从 0 层开始计数），则该层的节点数范围是 1 ~ 2ʰ 个。

举个例子：满二叉树是特殊的完全二叉树（最底层也填满了）；如果一棵二叉树有 3 层，前 2 层是满的，第 3 层有 3 个节点且都在最左边，那它也是完全二叉树。

另外，题目给出了 TreeNode 的定义（TypeScript 版本），大家可以先熟悉一下节点结构，后面代码解析会直接沿用这个定义：

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)
}
}

二、解法一：暴力遍历（BFS）—— 简单易上手

最直观的思路：不管是不是完全二叉树，只要遍历整棵树，把所有节点数加起来就行。这里我用「广度优先遍历（BFS，层序遍历）」来实现，适合刚接触二叉树的同学，逻辑简单，不容易出错。

1. 思路分析

BFS 的核心是「逐层遍历」：

这里有个小优化：初始时 count 可以设为 1（因为根节点存在时，至少有 1 个节点），后续只需要累加每一层子节点的个数，避免重复计数。

2. 完整代码

function countNodes_1(root: TreeNode | null): number {
if (!root) {
return 0; // 根节点为空，直接返回0
}
let count = 1; // 根节点存在，初始计数为1
let level = [root]; // 队列存储当前层节点，初始放入根节点
while (level.length) {
const nextLevel = []; // 存储下一层节点
for (const node of level) {
// 左子节点存在，加入下一层
if (node.left) {
nextLevel.push(node.left);
}
// 右子节点存在，加入下一层
if (node.right) {
nextLevel.push(node.right);
}
}
count += nextLevel.length; // 累加下一层节点数
level = nextLevel; // 切换到下一层继续遍历
}
return count;
};

3. 解法评价

✅ 优点：逻辑简单，代码易写易调试，适合新手入门，不需要利用完全二叉树的特性，通用性强（普通二叉树也能用）；

❌ 缺点：效率一般，时间复杂度 O(n)（需要遍历所有节点），空间复杂度 O(n)（队列最多存储一层的节点，最坏情况下是最底层，节点数接近 n/2）。

既然题目明确是「完全二叉树」，我们就可以利用它的特性，写出效率更高的解法。

三、解法二：二分查找 + 完全二叉树特性——优化到 O(log²n)

这是这道题的最优解法，核心思路是：完全二叉树的前 h-1 层是满二叉树，节点数可以直接用公式计算，只需要用二分查找确定最底层的节点个数即可。

1. 核心前提（完全二叉树特性）

假设完全二叉树的总层数为 h（从 0 层开始），那么：

• 前 h-1 层是满二叉树，满二叉树的节点总数公式为：2ʰ – 1（比如 h=3，前 2 层节点数是 2³ – 1 = 7）；

• 最底层（第 h 层）的节点数范围是 1 ~ 2ʰ，我们只需要找到最底层的实际节点数，加上前 h-1 层的节点数，就是总节点数。

2. 两步实现

步骤1：计算完全二叉树的层数 h（除去最底层的层数）

因为完全二叉树的最底层节点都在最左边，所以我们可以通过「一直向左遍历」来计算层数：

• 从根节点出发，每次只走左子节点，直到左子节点为空；

• 遍历的次数就是「除去最底层的层数」（比如遍历 2 次，说明前 2 层是满的，最底层是第 2 层）。

步骤2：二分查找最底层的节点数

最底层的节点可以看作是从 1 到 2ʰ 编号的节点（左到右依次编号），我们需要找到「最大的那个存在的节点编号」，这个编号就是最底层的实际节点数。

如何判断某个编号的节点是否存在？—— 利用节点编号的二进制特性：

• 假设最底层的节点编号范围是 [low, high]，low = 2ʰ（最底层第一个节点），high = 2^(h+1) – 1（最底层最后一个可能的节点）；

• 对于某个编号 k，将其转化为二进制，除去最高位的 1，剩下的每一位都对应「从根节点到该节点的路径」：0 表示走左子节点，1 表示走右子节点；

• 按照这个路径遍历，如果能找到节点，说明该编号的节点存在；否则不存在。

举个例子：h=2（最底层是第 2 层），k=5（二进制 101），除去最高位 1，剩下 01 → 路径是：根节点 → 左子节点 → 右子节点，若能走到最后，说明节点 5 存在。

3. 完整代码（主函数 + 辅助函数）

// 主函数：计算完全二叉树节点总数
function countNodes(root: TreeNode | null): number {
if (root === null) {
return 0; // 根节点为空，直接返回0
}
let level = 0;
let node = root;
// 步骤1：计算除去最底层的层数（前level层是满二叉树）
while (node.left !== null) {
level++;
node = node.left;
}

// 步骤2：二分查找最底层的节点数
// low：最底层第一个节点编号；high：最底层最后一个可能的节点编号
let low = 1 << level, high = (1 << (level + 1)) – 1;
while (low < high) {
const mid = (low + high + 1) >> 1; // 中间节点编号（向上取整，避免死循环）
if (exists(root, level + 1, mid)) { // 判断mid编号的节点是否存在
low = mid; // 存在，说明目标在mid右侧（包括mid）
} else {
high = mid – 1; // 不存在，说明目标在mid左侧
}
}
// 核心结论：low最终等于总节点数
return low;
};

// 辅助函数：判断编号为k的节点是否存在（level是总层数，从1开始计数）
const exists = (root: TreeNode | null, level: number, k: number): boolean => {
let bits = 1 << (level – 2); // 最高位的1对应的二进制位（用来判断路径方向）
let node = root;
while (node !== null && bits > 0) {
if (!(bits & k)) { // 该位为0，走左子节点
node = node.left;
} else { // 该位为1，走右子节点
node = node.right;
}
bits >>= 1; // 右移一位，判断下一位
}
return node !== null; // 能走到最后，说明节点存在
}

4. 关键细节解析（避坑重点）

• mid 的计算：用 (low + high + 1) >> 1 而不是 (low + high) >> 1，是为了向上取整，避免死循环。比如 low=4，high=5，mid=(4+5+1)/2=5，若节点5存在，low=5，循环结束；若用向下取整，mid=4，可能一直卡在 low=4、high=5。

• bits 的初始值：1 << (level – 2)，这里的 level 是「总层数」（从1开始），比如总层数是3，bits=2（10），对应最高位的1，用来判断第一个路径方向。

• 总节点数的简化：前面推导过，最终 low 的值就是总节点数，不需要再额外计算前 level 层的节点数，简化了代码。

5. 解法评价

✅ 优点：效率极高，时间复杂度 O(log²n)——计算层数是 O(logn)，二分查找是 O(logn)，每次二分查找中的节点存在性判断也是 O(logn)，整体是 logn * logn；空间复杂度 O(1)（只用到几个变量，没有递归或队列）。

❌ 缺点：逻辑相对复杂，需要理解完全二叉树的特性和节点编号的二进制路径，适合有一定二叉树和二分查找基础的同学。

四、两种解法对比 & 适用场景

五、总结

这道题的核心是「区分普通二叉树和完全二叉树的解法差异」—— 暴力遍历能解，但浪费了完全二叉树的特性；而最优解的关键的是抓住「前 h-1 层是满二叉树」，把问题转化为「二分查找最底层节点数」，从而将时间复杂度从 O(n) 优化到 O(log²n)。

建议大家先手写 BFS 解法，熟悉二叉树的层序遍历；再尝试理解二分查找的优化思路，重点搞懂「节点编号的二进制路径」和「exists 辅助函数」的逻辑，这样能更好地掌握二叉树和二分查找的结合运用。

如果觉得 exists 函数不好理解，可以找一个简单的完全二叉树（比如 3 层、5 个节点），手动模拟 k=3、k=4 等编号的判断过程，很快就能理清逻辑。