LeetCode Balanced Binary Tree：判斷平衡二叉樹

題目描述

給定二叉樹，判斷是否高度平衡：任意節點左右子樹高度差 ≤ 1。

解法：後序遍歷 + 剪枝

自底向上計算高度。若任一子樹不平衡（返回 -1），直接向上傳遞 -1。最終根節點返回 -1 即不平衡。

C++ 實現

class Solution {
    int treeDepth(TreeNode* root) {
        if (!root) return 0;
        int l = treeDepth(root->left);
        int r = treeDepth(root->right);
        if (l == -1 || r == -1) return -1;
        if (abs(l - r) > 1) return -1;
        return max(l, r) + 1;
    }
public:
    bool isBalanced(TreeNode* root) {
        return treeDepth(root) != -1;
    }
};

複雜度

• 時間：O(N)，每節點訪問一次。
• 空間：O(H) 遞歸棧，H 為樹高。