110. 平衡二叉樹

思路

平衡二叉樹的定義是：每一個節點的左樹高度與右樹高度差，都不超過一。

• $\text{abs(height(node}\to\text{left)} - \text{height(node}\to\text{left))}\leq1$
  在找節點的高度時，中途額外判斷是否平衡，並在最後回傳答案即可。

程式碼

遞迴

class Solution {
private:
    bool balance;
    int getHeight(TreeNode* node) {
        if(!balance || !node) { // 一旦不平衡, 返回的數值就不重要了
            return 0;
        }
        int leftHeight = getHeight(node->left);
        int rightHeight = getHeight(node->right);
        if(abs(leftHeight - rightHeight) > 1) {
            balance = false; // 根據上面的註解，在這裡也可以 return
        }
        return max(leftHeight, rightHeight) + 1;
    }
public:
    bool isBalanced(TreeNode* root) {       
        balance = true;
        getHeight(root);
        return balance;
    }
};

複雜度分析

• 時間複雜度：$O(n)$
• 空間複雜度：$O(H)$，$H$為樹的高度