如何高效统计完全二叉树的节点个数？

简化版

普通二叉树计数要遍历所有节点，时间 O(n)。完全二叉树可以利用“满二叉树节点数为 2^h - 1”的性质：比较左右子树高度，若某侧是满树就直接用公式计数，再递归另一侧，常见复杂度 O(log² n)。

详细版

对完全二叉树，沿最左边走得到高度。如果左子树高度等于右子树高度，说明左子树是满二叉树，可以直接加 2^leftHeight 个节点（根 + 左满树），再递归右子树；否则说明右子树是满二叉树，高度少一层，可以直接加 2^rightHeight 个节点，再递归左子树。

int countNodes(TreeNode root) {
    if (root == null) return 0;
    int left = height(root.left);
    int right = height(root.right);
    if (left == right) {
        return (1 << left) + countNodes(root.right);
    }
    return (1 << right) + countNodes(root.left);
}

int height(TreeNode node) {
    int h = 0;
    while (node != null) {
        h++;
        node = node.left;
    }
    return h;
}

这个优化只适用于完全二叉树，普通二叉树不能靠左右高度判断满树。

完整版教学

一、完全二叉树的结构约束

完全二叉树要求除了最后一层外，其余层都满，最后一层节点从左到右连续排列。这个约束非常强，它让某些子树必然是满二叉树。面试考点就在于：不要像普通树那样无脑遍历，而要利用结构省掉整块满树的遍历。

节点 2 的子树是满的，节点 3 的子树不是满的。通过高度关系可以判断哪一边可以直接套公式。

二、满二叉树为什么能 O(1) 计数

满二叉树每一层节点数是上一层的 2 倍。高度为 h 时，节点数是 1 + 2 + 4 + ... + 2^(h-1)，等比数列求和得到 2^h - 1。如果把当前根也一起算入，公式经常写成 1 + (2^h - 1) = 2^h。

h = 1: 1 = 2^1 - 1
h = 2: 1 + 2 = 3 = 2^2 - 1
h = 3: 1 + 2 + 4 = 7 = 2^3 - 1

这就是代码里 (1 << left) 的含义：当左子树高度是 left 且为满树时，根节点加左子树共 2^left 个节点。

三、为什么比较左右高度能判断哪边满

在完全二叉树中，左子树高度要么等于右子树高度，要么比右子树高 1。若二者相等，说明最后一层已经填到了右子树，左子树必然满；若左高右低，说明右子树虽然少一层，但右子树本身必然是满的。

leftHeight	rightHeight	哪边可直接计数	递归哪边
相等	相等	左子树 + 当前根	右子树
大 1	小 1	右子树 + 当前根	左子树

这个判断依赖“最后一层从左到右填充”。如果是普通二叉树，左右高度相等也不能说明左子树满。

四、复杂度为什么是 O(log² n)

每次递归会排除一棵满子树，只继续处理另一边，所以递归层数是树高 O(log n)。但每一层都要重新沿左边计算左右子树高度，每次高度计算也是 O(log n)。两者相乘就是 O(log² n)。

递归层数: log n
每层算高度: log n
总复杂度: O(log n * log n)

如果用二分最后一层节点是否存在，也可以做到 O(log² n)。两种方法本质上都在利用完全二叉树的层级结构。

五、位运算和溢出边界

1 << h 表示 2^h，但在 Java 中 int 左移如果高度太大会溢出。普通在线题的节点数通常在 int 范围内，但工程回答时可以提到用 long 更稳。高度的定义也要统一：空节点高度为 0，单节点高度为 1。

height(null) = 0
height(single) = 1
满树节点数 = 2^height - 1
根 + 满左子树 = 2^leftHeight

只要高度定义一致，代码里的公式就不会差一。

六、常见误区与追问

记忆钩子：完全二叉树计数的关键不是“数节点”，而是“发现哪一大块不用数”。

误区：完全二叉树和满二叉树一样。 完全二叉树最后一层可以不满，但必须从左到右连续。
误区：左右高度相等说明整棵树满。 这里只能推出左子树满，右子树仍可能不满。
误区：普通二叉树也能用这个优化。 普通树没有从左到右填充约束，高度判断不可靠。
误区：1 << h 永远安全。 高度较大时 int 可能溢出，可改用 1L << h。
追问：朴素 DFS 复杂度是多少？ 时间 O(n)，空间 O(h)，对完全二叉树没有利用结构。
追问：还能怎么做？ 可以二分最后一层位置，用路径判断节点是否存在，也是 O(log² n)。

七、加强记忆

这题记成“看高度，砍满树”。完全二叉树保证最后一层从左往右填，所以比较左右子树最左高度后，总有一边是满二叉树。满树用 2^h - 1 直接算，当前根一起合并成 2^h，剩下另一边继续递归，效率就从 O(n) 降到 O(log² n)。

简化版

详细版