完全二叉樹節點總數遞歸算法優化：避免重複判斷提升效率通過 OJ

原算法缺陷

int countNodes(TreeNode* root) {
    if (root == NULL) return 0;
    if (root->left == NULL) return 1;      // 錯誤：左為空不代表無右子樹
    if (root->right == NULL) return 2;     // 錯誤：右為空不代表僅有一個子節點
    return countNodes(root->left) + countNodes(root->right) + 1;
}

上述代碼對「只有左子樹」或「只有右子樹」的情況判斷邏輯錯誤，導致漏計節點，且遞歸深度大時超時。

正確通用遞歸寫法

int countNodes(TreeNode* root) {
    if (root == NULL) return 0;
    // 葉子節點
    if (root->left == NULL && root->right == NULL) return 1;
    // 至少有一個子樹非空
    return countNodes(root->left) + countNodes(root->right) + 1;
}

完全二叉樹專用優化 (O(log²n))

利用完全二叉樹性質：左/右子樹高度相等 → 滿二叉樹，節點數 = 2ʰ - 1；否則遞歸計算。

int getHeight(TreeNode* root) {
    int h = 0;
    while (root) { h++; root = root->left; }
    return h;
}

int countNodes(TreeNode* root) {
    if (!root) return 0;
    int lh = getHeight(root->left);
    int rh = getHeight(root->right);
    if (lh == rh) 
        return (1 << lh) + countNodes(root->right); // 左滿，右遞歸
    else 
        return (1 << rh) + countNodes(root->left);  // 右滿(高度差1)，左遞歸
}

總結

• 通用遞歸修正邏輯錯誤，適用於任意二叉樹。
• 完全二叉樹利用高度判斷可大幅降低時間複雜度，通過大數據量 OJ 測試。