222. Count Complete Tree Nodes

題目 / Problem

中文： 給你一棵完全二元樹的根節點 root，請回傳樹中節點的總數。

根據定義，完全二元樹的每一層（除了最後一層之外）都被完全填滿，而且最後一層的節點都盡量靠左排列。若最後一層是第 h 層，則它可以有 1 到 2^h 個節點。

題目要求：請設計一個時間複雜度小於 O(n) 的演算法。

English: Given the root of a complete binary tree, return the number of nodes in the tree.

In a complete binary tree, every level except possibly the last is completely filled, and all nodes in the last level are as far left as possible. If the last level is level h, it holds between 1 and 2^h nodes.

Requirement: design an algorithm that runs in less than O(n) time.

Constraints: - Number of nodes is in the range [0, 5 * 10^4]. - 0 <= Node.val <= 5 * 10^4. - The tree is guaranteed to be complete.

Worked example: root = [1,2,3,4,5,6] → output 6. The tree looks like:

        1
      /   \
     2     3
    / \   /
   4   5 6

There are 6 nodes, so the answer is 6.

名詞解釋 / Glossary

• 完全二元樹 / complete binary tree：一種特殊的二元樹，除了最後一層以外每層都填滿，且最後一層的節點全部靠左緊密排列。中間不會有「空洞」。這個性質是整個解法能加速的關鍵。 / A binary tree where every level but the last is full, and the last level fills left-to-right with no gaps. This regularity is what lets us beat O(n).
• 完美二元樹 / perfect binary tree：連最後一層也完全填滿的二元樹。若高度為 h（只有一個節點時 h=0），節點數剛好是 2^(h+1) − 1。 / A tree where even the last level is completely full. A perfect tree of height h has exactly 2^(h+1) − 1 nodes.
• 樹高 / height：從某節點一路往下走到最深葉子所經過的「邊」數。這裡我們用「一直往左走能走幾步」來量高度。 / The number of edges on the longest downward path. We measure it by counting how many steps we can walk purely left.
• 遞迴 / recursion：函式呼叫自己來解決規模較小的子問題（例如左子樹、右子樹）。 / A function calling itself to solve smaller subproblems (the left and right subtrees).
• 位元左移 / bit shift <<：1 << k 代表 2 的 k 次方。它是把二進位的 1 往左推 k 位，比用迴圈算次方更快。 / 1 << k equals 2^k; it slides the binary bit 1 left by k positions — a fast way to compute a power of two.
• 指標 / pointer (TreeNode*)：一個存放「節點所在記憶體位址」的變數。node->left 表示「順著指標找到那個節點，再取它的 left 欄位」。NULL 表示空、沒有節點。 / A variable holding a node's memory address. node->left follows the pointer and reads its left field; NULL means "no node."

思路

中文： 最直覺的做法是把每個節點都走一遍（DFS 或 BFS），邊走邊數，這是 O(n)。它一定正確，但題目明確要求「小於 O(n)」，所以我們必須利用「完全二元樹」這個額外條件來偷懶。

關鍵觀察：如果一棵樹是「完美」的（最後一層也滿），那我們不用數，直接套公式。只要一路往左走量出高度 hL，一路往右走量出高度 hR，當 hL == hR 時代表整棵樹是完美的，節點數就是 2^(hL+1) − 1。這一步只花 O(h) = O(log n) 時間，一次搞定整棵子樹。

那如果 hL != hR（左邊比右邊深，代表最後一層沒填滿）呢？這時我們就退回遞迴：總數 = 1（自己）+ 左子樹節點數 + 右子樹節點數。看起來像是又變回 O(n)，但巧妙之處在於：因為是完全二元樹，每次往下遞迴時，左右子樹裡最多只有一棵是「不完美」的，另一棵一定完美、可以馬上用公式算掉。所以真正需要繼續遞迴的路徑只有一條，深度是 O(log n)，而每一層都花 O(log n) 去量高度，總共是 O(log n × log n) = O(log²n)，遠小於 O(n)。

English: The naive approach visits every node (DFS/BFS) and counts — that's O(n). It's correct but the problem explicitly demands sub-linear time, so we must exploit the "complete tree" structure.

Key insight: if a subtree is perfect (even its last level is full), we skip counting and use a formula. Walk all the way left to get height hL, all the way right to get height hR. When hL == hR, the subtree is perfect and holds exactly 2^(hL+1) − 1 nodes. Measuring those two heights costs only O(h) = O(log n), and it settles the whole subtree at once.

When hL != hR (the left spine is deeper, meaning the last level isn't full), we fall back to recursion: total = 1 (this node) + count(left) + count(right). This looks like it degrades back to O(n), but here's the trick: in a complete tree, at most one of the two children's subtrees is imperfect — the other is always perfect and gets resolved instantly by the formula. So only a single path actually keeps recursing, giving depth O(log n), and each level spends O(log n) measuring heights. Total: O(log n × log n) = O(log²n), comfortably under O(n).

逐步走查 / Walkthrough

Input: root = [1,2,3,4,5,6] (the tree drawn above). We call countNodes(node).

重要修正 / Careful: 對節點 1，往左走 1 → 2 → 4 是 2 步，往右走 1 → 3 → 6 是 2 步。但節點 5、6 之後就沒有左孩子了，最後一層其實沒填滿。左右最左路徑與最右路徑長度相等不代表完美嗎？在完全樹裡，最右一路往右走若和最左一路往左走一樣長，就保證是完美的——但這棵樹往右走 3→6，6 沒有右孩子，所以往右到底其實只有 1→3→6... 讓我們精確量：

• hL (一直往左)：1 → 2 → 4，停在 4（無左孩子）。步數 = 2。
• hR (一直往右)：1 → 3 → 6？不對，3 的右孩子是空的（3 只有左孩子 6）。所以 1 → 3，3 無右孩子，停在 3。步數 = 1。

注意整個過程只有 1 → 3 這一條「不完美路徑」真正深入遞迴，2 這棵子樹一步就用公式算完了。/ Note only the single imperfect path 1 → 3 truly recurses; subtree 2 is settled in one formula step.

Solution — C

/*
 * 演算法 / 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);
}

Solution — C++

/*
 * 演算法 / 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);
    }
};

複雜度 / Complexity

• Time: O(log²n) — 樹高 h = O(log n)（因為完全樹很「矮胖」）。真正需要遞迴的只有一條從根到葉的路徑，長度 O(log n)；在這條路徑的每一層，我們都花 O(log n) 去量左右脊高度。兩者相乘即 O(log n × log n) = O(log²n)。其餘子樹在遇到時一步用公式解決，不展開。 / The tree height is h = O(log n). Only a single root-to-leaf path recurses (length O(log n)), and each level along it spends O(log n) measuring the two spines — hence O(log²n). Every other subtree is dispatched in one formula step.
• Space: O(log n) — 遞迴呼叫堆疊的最大深度等於樹高 O(log n)，量高度用的迴圈只用常數額外空間。 / The recursion call stack goes as deep as the tree height, O(log n); the height-measuring loops use only constant extra space.

Pitfalls & Edge Cases

• 空樹 / Empty tree (root == NULL)：一開始就要判斷並回傳 0，否則後面 root->left 會解參考空指標而崩潰。/ Check for null first and return 0; otherwise root->left dereferences a null pointer and crashes.
• 量高度必須沿「純左」與「純右」脊 / Measure heights along the pure-left and pure-right spines：不能隨便走，只有這兩條路徑等長才等價於「完美」。走錯路徑會誤判。/ You must follow the leftmost and rightmost paths specifically — only those being equal proves perfection.
• 位移溢位 / Shift overflow：1 << (h+1) 若用 32 位 int 且 h 很大可能溢位。本題節點上限 5×10⁴（高度約 16）雖安全，但用 long/1LL 是穩健習慣。/ 1 << (h+1) can overflow a 32-bit int for large h; using long/1LL is the safe habit even when the range is small.
• 公式別記錯 / Don't misremember the formula：hL 是「邊數」而非「層數」。高度 h（單一節點時 h=0）的完美樹有 2^(h+1) − 1 個節點，別漏掉 +1 或 −1。/ hL counts edges, not levels. A perfect tree of height h (h=0 for a single node) has 2^(h+1) − 1 nodes — keep both the +1 and the −1.
• 別退化成 O(n) / Don't accidentally count every node：若省略「完美就套公式」這一步而永遠遞迴到底，就變回 O(n)，不符題目要求。公式捷徑正是加速的來源。/ Skipping the "perfect ⇒ formula" shortcut collapses back to O(n); that shortcut is the whole point.