LeetCode 222 完全二叉樹節點計數：從暴力遞歸到 O(log²n) 優化解法

題目背景與定義

LeetCode 222 Count Complete Tree Nodes 要求計算完全二叉樹的節點總數。根據維基百科定義：完全二叉樹除最後一層外，每一層都被完全填滿，且最後一層的所有節點都靠左排列。若樹高為 h，最後一層節點數介於 1 到 2ʰ 之間。

初始嘗試：前序遍歷（超時）

最直觀的做法是遍歷整棵樹，例如前序遍歷收集所有節點再計數：

public class Solution {
    public int countNodes(TreeNode root) {
        List<TreeNode> list = preOrder(root);
        return list.size();
    }

    public List<TreeNode> preOrder(TreeNode root) {
        List<TreeNode> list = new ArrayList<>();
        if (root == null) return list;
        list.add(root);
        if (root.left != null)  list.addAll(preOrder(root.left));
        if (root.right != null) list.addAll(preOrder(root.right));
        return list;
    }
}

此解法時間複雜度 O(n)，空間複雜度 O(n)（遞歸棧 + 列表），在節點數極大時會超時。

優化思路：利用完全二叉樹性質

完全二叉樹的關鍵特性：左子樹高度恆 ≥ 右子樹高度，且左右子樹至少有一棵是滿二叉樹。

• 若左、右子樹高度相等 → 左子樹是高度 h-1 的滿二叉樹，節點數 = 2ʰ⁻¹ - 1，遞歸處理右子樹。
• 若左子樹高度大於右子樹 → 右子樹是高度 h-2 的滿二叉樹，節點數 = 2ʰ⁻² - 1，遞歸處理左子樹。

每次遞歸只深入一邊，高度計算僅沿左/右邊緣向下，單次高度 O(log n)，遞歸深度 O(log n)，總時間複雜度 O(log² n)，空間複雜度 O(log n)（遞歸棧）。

優化實現（Java）

public class Solution {
    public int countNodes(TreeNode root) {
        if (root == null) return 0;
        int leftH = height(root.left);
        int rightH = height(root.right);
        if (leftH == rightH) {
            // 左子樹滿，節點數 2^leftH - 1 + 1(根) + 右子樹遞歸
            return (1 << leftH) + countNodes(root.right);
        } else {
            // 右子樹滿，節點數 2^rightH - 1 + 1(根) + 左子樹遞歸
            return (1 << rightH) + countNodes(root.left);
        }
    }

    private int height(TreeNode node) {
        int h = 0;
        while (node != null) {
            h++;
            node = node.left; // 完全二叉樹最左路徑即高度
        }
        return h;
    }
}

關鍵點總結

1. 不要遍歷所有節點，利用「完全」性質跳過滿子樹。
2. 高度計算只走左邊緣，因為完全二叉樹最後一層靠左，最左路徑長度即樹高。
3. 位運算 1 << h 等價於 2ʰ，避免 Math.pow 浮點誤差。
4. 若面試要求迭代寫法，可用 while 循環模擬遞歸，邏輯相同。

複雜度對比

掌握此題核心在於「識別滿子樹並直接計算」，同類技巧常見於完全二叉樹、堆相關題目。