/*
 * 演算法 / Algorithm:
 * 1) 量最左路徑高度 hL 與最右路徑高度 hR。
 *    Measure left-spine height hL and right-spine height hR.
 * 2) 若 hL==hR，子樹是完美的，直接回傳 2^(hL+1)-1（用位移計算）。
 *    If hL==hR the subtree is perfect: return 2^(hL+1)-1 via bit shift.
 * 3) 否則遞迴：1 + 左子樹 + 右子樹。完全樹保證只有一邊不完美，故為 O(log^2 n)。
 *    Else recurse: 1 + left + right. Only one side is imperfect → O(log^2 n).
 */

// LeetCode 已定義的節點結構（此處僅示意）/ Node struct as defined by LeetCode (shown for reference).
// struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; };

int countNodes(struct TreeNode* root) {
    // 空樹沒有節點，直接回傳 0。root 是指標，NULL 代表指向「空」。
    // Empty tree has 0 nodes. root is a pointer; NULL means it points to nothing.
    if (root == NULL) return 0;

    // hL 用來記錄「一直往左走」的步數（左脊高度）。
    // hL counts steps taken by always going left (height of the left spine).
    int hL = 0;
    // p 是一個遊走用的指標，先從左孩子開始。
    // p is a walking pointer; start at the left child.
    struct TreeNode* p = root->left;
    // 只要還沒走到空，就繼續往左，並把步數 +1。
    // While not yet NULL, keep going left and increment the step count.
    while (p != NULL) {
        hL++;              // 多走一步 / one more step down
        p = p->left;       // 順著指標移到下一個左孩子 / follow pointer to next left child
    }

    // hR 同理，記錄「一直往右走」的步數（右脊高度）。
    // hR likewise counts steps by always going right (height of the right spine).
    int hR = 0;
    p = root->right;       // 這次從右孩子開始 / start at the right child this time
    while (p != NULL) {
        hR++;              // 往下一步 / one step down
        p = p->right;      // 移到下一個右孩子 / move to next right child
    }

    // 若左右脊一樣高，整棵子樹是「完美」的，可用公式秒算。
    // Equal spine heights ⇒ subtree is perfect ⇒ use the closed-form formula.
    if (hL == hR) {
        // 節點數 = 2^(hL+1) - 1。(1 << k) 就是 2 的 k 次方，比迴圈算次方快。
        // Count = 2^(hL+1) - 1. (1 << k) equals 2^k — a fast power of two.
        // 用 long 避免中間計算溢位（雖然本題範圍不會，但養成好習慣）。
        // Use long to avoid overflow in the shift (safe habit even if range is small).
        return (int)(((long)1 << (hL + 1)) - 1);
    }

    // 不完美：回退到遞迴。1 代表 root 自己，再加上左右子樹的節點數。
    // Imperfect: fall back to recursion. 1 is root itself, plus both subtrees.
    return 1 + countNodes(root->left) + countNodes(root->right);
}