判斷平衡二叉樹：O(n²) 與 O(n) 兩種遞歸方案對比

問題定義

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

方案一：自頂向下遞歸 O(n²)

對每個節點，分別計算左右子樹深度，再遞歸判斷左右子樹是否平衡。

int TreeDepth(TreeNode* root) {
    if (!root) return 0;
    int left = TreeDepth(root->left);
    int right = TreeDepth(root->right);
    return max(left, right) + 1;
}

bool IsBalanced(TreeNode* root) {
    if (!root) return true;
    if (!IsBalanced(root->left)) return false;
    if (!IsBalanced(root->right)) return false;
    int leftDepth = TreeDepth(root->left);
    int rightDepth = TreeDepth(root->right);
    return abs(leftDepth - rightDepth) <= 1;
}

缺點：深度被重複計算多次，時間復雜度 O(n²)（斜樹最壞情況）。

方案二：自底向上遞歸 O(n)

在判斷平衡的同時計算深度，通過引用參數返回子樹深度，避免重複遍歷。

bool IsBalancedCore(TreeNode* root, int& depth) {
    if (!root) {
        depth = 0;
        return true;
    }
    int leftDepth, rightDepth;
    if (!IsBalancedCore(root->left, leftDepth)) return false;
    if (!IsBalancedCore(root->right, rightDepth)) return false;
    
    depth = max(leftDepth, rightDepth) + 1;
    return abs(leftDepth - rightDepth) <= 1;
}

bool IsBalancedTree(TreeNode* root) {
    int depth;
    return IsBalancedCore(root, depth);
}

核心差異對比

關鍵點總結

• 平衡二叉樹判斷本質是後序遍歷：先處理子樹，再處理根節點
• 方案二利用引用參數傳遞深度，實現「一遍遍歷，同時完成判斷與深度計算」
• 若需輸出具體不平衡節點，可修改返回結構體包含 (isBalanced, depth, unbalancedNode)