完全二叉树的节点个数

下面 9 步动画会按主解代码推进，而不是泛泛讲题型。

1. 读入完全二叉树：示例是完全二叉树 [1,2,3,4,5,6]，共 6 个节点。目标：不逐个遍历，用高度性质整块计数。先从根 1 开始。

2. 量左右最左高度：量高度时沿最左链向下：左链 1→2→4 得 lh=2，右子树最左链 3→6 得 rh=2(图中蓝色标出这两条路径)。

3. lh==rh → 左子树满：lh==rh=2 → 左子树是高度 2 的满树。根 1 加左子树整块共 2^2 = 4 个节点，一次性计数完成；接着只递归右子树 3。

4. 递归右子树 3：递归进入右子树 3(调用栈压入 countNodes(3))。在 3 处量高度：左链 3→6 得 lh=1，右子为空得 rh=0。

5. lh≠rh → 右子树满：lh(1) 不等于 rh(0) → 节点 3 的右子树是满树(为空)。含节点 3 这一块计 2^0 = 1 个；再递归左子树 6。

6. 递归到叶子 6：递归进入 6(调用栈压入 countNodes(6))。6 是叶子：左右最左高度都为 0，相等。

7. 6 返回 1：6 是叶子，lh==rh==0：(1<<0) + countNodes(空) = 1 + 0 = 1，节点 6 计数完成、出栈。

8. 回收求和：逐层回收求和：countNodes(3) = 1(自身块) + 1(来自 6) = 2；countNodes(1) = 4 + 2 = 6。全 6 个节点均已计数。

9. 返回 6：返回 6。每次只沿最左路径量高度并整块跳过，时间 O(log²n)、栈空间 O(log n)。

记住这题的代码骨架：题意约束先落到状态变量，再用循环或递归维护它。