WEI-CHENG CHEN

解法

自底向上（bottom-up）+ 後序遍歷

1. 從葉節點開始往上回傳高度
2. 每個節點都檢查左右子樹高度差是否 ≤ 1
3. 若任何一個節點不平衡，整棵樹就不平衡

class Solution {
public:
    int DFS(TreeNode* root){
        // 終止條件
        if(!root) return 0;
        // 先由根結點往下伸
        int left_subtree = DFS(root->left);
        int right_subtree = DFS(root->right);

        // 遞迴回來的部分 => 開始做檢查
        // 如果左或右子樹已經不平衡，直接回傳 -1
        if(left_subtree==-1 || right_subtree==-1) return -1;
        // 如果當前節點左右高度差 > 1，也是不平衡
        if(abs(right_subtree-left_subtree)>1) return -1;

        return max(left_subtree, right_subtree)+1; // 左右子樹比較高的那個， 再加上「自己這一層」
    }
    bool isBalanced(TreeNode* root) {
        return DFS(root) != -1;
    }
};