LeetCode 222 Count Complete Tree Nodes：利用完全二叉樹性質 O(log²n) 計數

題目大意

給定完全二叉樹根節點，求節點總數。完全二叉樹：除最後一層外滿，最後一層靠左排列。

核心思路

• 計算左子樹高度 `lh`（沿左孩子一直走）和右子樹高度 `rh`（沿右孩子一直走）。
• 若 `lh == rh`：左子樹為完美二叉樹，節點數 = `2^lh - 1`，加上根節點 1，遞歸計算右子樹。
   `count = (1 << lh) + countNodes(root->right)`
• 若 `lh > rh`：右子樹為完美二叉樹（高度 `rh`），遞歸計算左子樹。
   `count = (1 << rh) + countNodes(root->left)`

代碼實現

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int getHeight(TreeNode* root) {
        int h = 0;
        while (root) { root = root->left; ++h; }
        return h;
    }
    int countNodes(TreeNode* root) {
        if (!root) return 0;
        int lh = getHeight(root->left);
        int rh = getHeight(root->right);
        if (lh == rh) return (1 << lh) + countNodes(root->right);
        else return (1 << rh) + countNodes(root->left);
    }
};

複雜度

• 每層遞歸計算高度 `O(log n)`，遞歸深度 `O(log n)`。
• 總時間 O(log² n)，空間 O(log n)（遞歸棧）。