題目網址：https://leetcode.cn/problems/balanced-binary-tree/

題意：給一 BT, 判斷它是否 height-balanced。

height-balanced 的定義：BT 中每個 node 的左、右子樹的高度差不超過 1。

Solution：

想法：利用 DFS, 如果當前 node 的左、右子樹的高度差不超過 1, 且左、右子樹皆為 height-balanced, 則返回 true

class Solution {
public:
    bool isBalanced(TreeNode* root) {
        if (!root) {
            return true;
        }

        const int left = height(root->left);
        const int right = height(root->right);

        return abs(left - right) <= 1 &&
               isBalanced(root->left) &&
               isBalanced(root->right);
    }

private:
    int height(const TreeNode* root){
        if (!root) {
            return 0;
        }

        const int left = height(root->left);
        const int right = height(root->right);

        return 1 + max(left, right);
    }
};
  • time：$O(n)$ ➔ 遍歷 BT 中所有 node
  • space：$O(n)$ ➔ 取決於遞迴深度, worse case：BT 為 skew tree