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

每次遞歸至少一邊是滿樹，可直接計算，深度 O(log n)，每層計算高度 O(log n)，總時間 O(log² n)。

代碼實現

public int countNodes(TreeNode root) {
    if (root == null) return 0;
    int leftH = 0, rightH = 0;
    TreeNode p = root;
    while (p != null) { leftH++; p = p.left; }
    p = root;
    while (p != null) { rightH++; p = p.right; }
    if (leftH == rightH) return (1 << leftH) - 1;
    return 1 + countNodes(root.left) + countNodes(root.right);
}

複雜度分析

時間 O(log² n)，空間 O(log n) 遞歸棧。遠優於 O(n) 遍歷。