LeetCode 222. 完全二叉树的节点个数
目录
题目描述
题意分析
要求返回一棵二叉树的节点总数。如果题目只说「二叉树」，那么除了遍历一遍数出来别无他法，$O(n)$ 已经是下界。但题目给出的前提是完全二叉树：除最后一层外每一层都被填满，且最后一层的节点全部靠左连续排列。这个前提不是背景描述，而是本题唯一的题眼——它把「形状」的自由度压到了极低，使得只用高度信息就能推断出大片区域的节点数，从而做到比 $O(n)$ 更快。
因此这道题的隐含要求是：写出一个严格优于 $O(n)$ 的解法。层序遍历或递归遍历虽然能过，但完全没有用到「完全」这个条件，面试中会被直接追问「你怎么利用完全二叉树的性质」。目标复杂度是 $O(\log^2 n)$。
边界上要考虑：空树返回 $0$；只有根节点的树返回 $1$；以及最后一层只填了一个节点（左链最深、右链浅一层）这类最不平衡的情形，它会让判据频繁失效，是检验剪枝逻辑是否正确的关键用例。另外节点数可达数万，高度不超过 $17$，用位运算算 $2^h$ 不会溢出，但也要意识到这个前提。
解法：利用满二叉树高度剪枝
核心思路
普通二叉树只能逐个计数，但完全二叉树包含大量满二叉树。对当前子树分别沿最左链、最右链计算高度：在「当前子树完全」的前提下，两者相等说明所有层都已填满，可以直接用 $2^h-1$ 计算节点数；不相等时再递归统计左右子树。
这个递归不会退化为遍历全部节点。完全二叉树的最后一层从左向右连续填充：若节点已进入右子树，则左子树必满；否则右子树必是少一层的满树。因此每层至多只有一棵子树继续递归，另一棵会被公式立即算完。
不变量：每次递归处理的仍是完全二叉树，所以「左右边界高度相等即可判满」始终成立。这里的高度按节点数计算，单节点高度为 $1$，才能与公式 $2^h-1$ 配套。
解题步骤
- 空节点返回 $0$。
- 分别计算当前子树最左链和最右链的节点数。
- 高度相等时，当前子树是满树，返回
(1 << height) - 1。- 高度不等时，返回左子树节点数、右子树节点数与根节点之和。
例如
[1,2,3,4,5,6]：根的左右边界高度分别为 $3$、$2$，不能直接套公式；左子树[2,4,5]的两条边界高度同为 $2$，直接计为 $3$；右子树递归计为 $2$，最终得到 $6$。
代码实现
class Solution {
public int countNodes(TreeNode root) {
if (root == null) {
return 0;
}
int leftHeight = leftHeight(root);
int rightHeight = rightHeight(root);
if (leftHeight == rightHeight) {
return (1 << leftHeight) - 1;
}
return countNodes(root.left) + countNodes(root.right) + 1;
}
private int leftHeight(TreeNode node) {
int height = 0;
while (node != null) {
height++;
node = node.left;
}
return height;
}
private int rightHeight(TreeNode node) {
int height = 0;
while (node != null) {
height++;
node = node.right;
}
return height;
}
}
func countNodes(root *TreeNode) int {
if root == nil {
return 0
}
left := leftHeight(root)
right := rightHeight(root)
if left == right {
return (1 << left) - 1
}
return countNodes(root.Left) + countNodes(root.Right) + 1
}
func leftHeight(node *TreeNode) int {
height := 0
for node != nil {
height++
node = node.Left
}
return height
}
func rightHeight(node *TreeNode) int {
height := 0
for node != nil {
height++
node = node.Right
}
return height
}
复杂度分析
- 时间复杂度：$O(\log^2 n)$。递归深度为 $O(\log n)$，每层计算两条边界高度还需 $O(\log n)$。
- 空间复杂度：$O(\log n)$，来自递归调用栈；完全二叉树的高度为 $O(\log n)$。
关键点总结
- 「边界高度相等则满」依赖完全二叉树前提，不能套到任意二叉树。
- 满子树用公式整体跳过，才真正利用了题目给出的结构性质。
- 高度计数口径必须与公式一致：本文按节点数计高。
- $O(\log^2 n)$ 来自「递归 $O(\log n)$ 层 × 每层计算高度 $O(\log n)$」。
易错点总结
- 把高度按边数计算，却仍使用
(1 << h) - 1：单节点会被算成 $0$；按边数计高时指数应为 $h+1$。- 只算左链高度就套满树公式：
[1,2,3,4,5,6]会误算成 $7$。- 满树公式忘记减一：高度为 $2$ 的满树应有 $3$ 个节点，而不是 $4$ 个。
- 非满分支忘记加当前根节点：每次递归都会少计一个。
- 在普通二叉树上使用该判据：左右边界等高也可能内部缺节点，结论不成立。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 919. 完全二叉树插入器 | 中等 | 维护完全二叉树的插入位置，用队列缓存待补孩子的节点 |
| LCR 043. 完全二叉树插入器 | 中等 | 与 919 同题，另可用节点编号的二进制位定位插入路径 |