/*
 * 演算法 / Algorithm:
 * 量左脊高度 hL 與右脊高度 hR。相等 → 子樹完美，回傳 2^(hL+1)-1；
 * 不相等 → 遞迴 1 + 左 + 右。完全樹保證僅一側不完美，故 O(log^2 n)。
 * Measure left/right spine heights. Equal → perfect subtree, return 2^(hL+1)-1;
 * otherwise recurse 1 + left + right. Completeness ⇒ one imperfect side ⇒ O(log^2 n).
 */

class Solution {
public:
    int countNodes(TreeNode* root) {
        // 空指標代表空樹，節點數為 0。/ A null pointer is an empty tree: 0 nodes.
        if (root == nullptr) return 0;

        // 量左脊：從左孩子出發一路往左，直到走到 nullptr。
        // Measure the left spine: from the left child, keep going left until nullptr.
        int hL = 0;
        for (TreeNode* p = root->left; p != nullptr; p = p->left) {
            ++hL;   // 每往下一層就 +1 / +1 for each level descended
        }

        // 量右脊：從右孩子出發一路往右。/ Measure the right spine: keep going right.
        int hR = 0;
        for (TreeNode* p = root->right; p != nullptr; p = p->right) {
            ++hR;
        }

        // 左右脊等高 ⇒ 完美二元樹，直接套公式。
        // Equal spines ⇒ perfect tree ⇒ apply the closed-form formula.
        if (hL == hR) {
            // 1LL << k 是 long long 型別的 2^k，避免位移時溢位。
            // 1LL << k is 2^k as a long long, guarding the shift against overflow.
            return static_cast<int>((1LL << (hL + 1)) - 1);
        }

        // 不完美：遞迴計數。auto 讓編譯器自動推導型別，此處即 int。
        // Imperfect: recurse. 1 (this node) + left subtree + right subtree.
        return 1 + countNodes(root->left) + countNodes(root->right);
    }
};