02、完全二叉树的节点个数

如果不利用树的结构，统计节点就是一次遍历。完全二叉树的特殊之处在于：有些子树不必继续逐个数，只要识别出它已经填满，就能直接计算节点数。

问题与前提

LeetCode 222：完全二叉树的节点个数给定一棵完全二叉树，返回节点数。完全二叉树除最后一层外全部填满，最后一层的节点从左向右连续排列。

       1
     /   \
    2     3
   / \   /
  4   5 6

这棵树有 6 个节点，是完全二叉树，但不是每一层都填满的完美二叉树。本文说的“满子树”指每层都填满、节点数为 2^h - 1 的子树，避免与“每个节点度数为0或2”的另一种术语约定混淆。

普通遍历为什么总是可行

任何二叉树都能使用 1 + 左子树节点数 + 右子树节点数。每个节点访问一次，时间 O(n)，递归栈空间 O(h)。这是理解后续优化以及验证结果的基础，不要一开始就只记位移公式。

比较两条极端路径

从某个子树根分别一直走 left、一直走 right，得到左高与右高，高度均按节点个数计算。

• 高度相同：在完全二叉树前提下，这个子树每层都填满，直接返回 2^h - 1。
• 高度不同：不能直接套公式，继续统计左右子树，再加根节点。

在六节点的例子中执行

根 1 的左高为 3、右高为 2，不能直接计算整树。继续看节点 2，它的左高、右高都为 2，所以直接得到 3 个节点。节点 3 的左右高度不同，再拆成根 3 与节点 6，得到 2。最终 1 + 3 + 2 = 6。

这个结论不能脱离输入前提：一棵任意二叉树的最左与最右路径等高，中间仍可能缺节点，因此不能仅凭两条路径证明它填满了。

C++17 实现

题目节点数量上限为 5 × 10⁴，下面的高度移位和返回值在这个范围内足够。

struct TreeNode {
  int val = 0;
  TreeNode* left = nullptr;
  TreeNode* right = nullptr;
};

class Solution {
 public:
  int countNodes(TreeNode* root) {
    if (root == nullptr) return 0;
    int left_height = 0;
    int right_height = 0;
    for (TreeNode* node = root; node != nullptr; node = node->left) {
      ++left_height;
    }
    for (TreeNode* node = root; node != nullptr; node = node->right) {
      ++right_height;
    }
    if (left_height == right_height) {
      return static_cast<int>((1LL << left_height) - 1);
    }
    return 1 + countNodes(root->left) + countNodes(root->right);
  }
};

为什么是 O(log²n)

完全二叉树高度为 O(log n)。每次拆分时，至少有一边能识别成满子树并停止向下展开，只有另一边继续深入；每层的高度检查又花 O(log n) 以内的时间，因此总时间 O(log² n)，递归栈 O(log n)。

不是因为“代码有递归”就一定要遍历全部节点，也不是因为用了位移就整体 O(1)。空树为 0，单节点高度为 1、节点数为 1，正好能检查高度与公式是否统一。

常见误区

高度按边数计却仍使用 2^h - 1，会少算一层；对任意树直接用本算法，可能把中间缺失的节点也算进去。面试表达中先说清“完全二叉树”这个前提，再解释优化才完整。