LeetCode 平衡二叉樹判定：遞歸計算深度與剪枝優化

LeetCode Balanced Binary Tree：判定二叉樹是否高度平衡

題目要求

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

遞歸分析

樹的問題天然適合遞歸。需對每個節點檢查：

1. 左子樹是否平衡
2. 右子樹是否平衡
3. 左右子樹高度差 ≤ 1

初級解法：分離深度計算與平衡判定

class Solution {
public:
    bool isBalanced(TreeNode* root) {
        if (!root) return true;
        if (abs(depth(root->left) - depth(root->right)) > 1) return false;
        return isBalanced(root->left) && isBalanced(root->right);
    }
    int depth(TreeNode* root) {
        if (!root) return 0;
        return max(depth(root->left), depth(root->right)) + 1;
    }
};

缺點： 重複計算子樹高度，時間復雜度 O(n²)（斜樹情況）。

優化解法：後序遍歷 + 剪枝（自底向上）

在計算深度時同步檢查平衡，一旦發現不平衡立即返回標記值（如 -1），避免無效遞歸：

class Solution {
public:
    bool isBalanced(TreeNode* root) {
        return checkHeight(root) != -1;
    }
    int checkHeight(TreeNode* node) {
        if (!node) return 0;
        int leftH = checkHeight(node->left);
        if (leftH == -1) return -1;
        int rightH = checkHeight(node->right);
        if (rightH == -1) return -1;
        if (abs(leftH - rightH) > 1) return -1;
        return max(leftH, rightH) + 1;
    }
};

優勢： 每節點僅訪問一次，時間 O(n)，空間 O(h)（遞歸棧深度）。

關鍵點總結

• 平衡定義：所有節點 滿足高度差 ≤ 1，非僅根節點
• 後序遍歷（左→右→根）天然適合自底向上聚合信息
• 用特殊返回值（-1）傳遞「不平衡」信號，實現剪枝