判斷平衡二叉樹：自頂向下 O(N log N) vs 自底向上 O(N) 兩種遞歸解法對比

問題定義

輸入一棵二叉樹的根節點，判斷該樹是否為平衡二叉樹：任意節點的左右子樹高度差不超過 1。

方案一：自頂向下（朴素遞歸）

思路：對每個節點分別計算左右子樹高度，檢查差值，再遞歸檢查左右子樹。

程式碼

int getDepth(TreeNode* root) {
    if (!root) return 0;
    return max(getDepth(root->left), getDepth(root->right)) + 1;
}
bool isBalancedTopDown(TreeNode* root) {
    if (!root) return true;
    int lh = getDepth(root->left);
    int rh = getDepth(root->right);
    if (abs(lh - rh) > 1) return false;
    return isBalancedTopDown(root->left) && isBalancedTopDown(root->right);
}

複雜度分析

• 每個節點被 getDepth 重複訪問多次。
• 最壞情況（斜樹/滿樹）：O(N^2)；平均 O(N log N)。
• 空間：遞歸棧 O(H)，H 為樹高。

方案二：自底向上（後序遍歷 + 剪枝）

核心優化：後序遍歷（左→右→根），在返回時同時計算高度並檢查平衡。若發現不平衡，立即向上傳遞失敗訊號（如返回 -1），避免多餘計算。

程式碼

// 返回值：-1 表示不平衡；>=0 表示該子樹高度
int checkBalance(TreeNode* root) {
    if (!root) return 0;
    int lh = checkBalance(root->left);
    if (lh == -1) return -1;
    int rh = checkBalance(root->right);
    if (rh == -1) return -1;
    if (abs(lh - rh) > 1) return -1;
    return max(lh, rh) + 1;
}
bool isBalancedBottomUp(TreeNode* root) {
    return checkBalance(root) != -1;
}

複雜度分析

• 每個節點**僅訪問一次** → 時間 O(N)。
• 空間：遞歸棧 O(H)，最壞 O(N)（斜樹）。
• 可改寫為迭代後序遍歷將空間優化為 O(1)（Morris 遍歷），但程式碼複雜度大增，通常遞歸足夠。

兩種解法對比總結

進階：迭代版後序遍歷（避免棧溢位）

對於極深樹（N > 10^5），遞歸可能棧溢位。可使用顯式棧模擬後序遍歷，維護 pair<TreeNode*, int> 記錄狀態（0=未訪左，1=未訪右，2=可處理根），同樣實現 O(N) 時間、O(H) 空間。

測試用例建議

• 空樹 → true
• 單節點 → true
• 完全二叉樹 → true
• 左斜樹（鏈表） → false (高度差 > 1)
• 根左右高度差為 2 的樹 → false
• 大型隨機平衡樹 → true（驗證效能）

總結

判斷平衡二叉樹，**自底向上後序遍歷是最佳實踐**：單次遍歷、即時剪枝、程式碼簡潔。面試中先寫朴素版說明思路，再優化為 O(N) 版本並解釋複雜度差異，展現對遞歸與樹遍歷的深度理解。