【ATT】 Balanced Binary Tree

    bool isBalanced(TreeNode *root) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        return (getHeight(root)>=0)? true: false;      
    }
    
    int getHeight(TreeNode *root)
    {
        if(!root) return 0;
        int leftHeight = getHeight(root->left);
        int rightHeight = getHeight(root->right);
        if(leftHeight<0||rightHeight<0||abs(leftHeight-rightHeight)>1)   //该子树不平衡，返回-1
            return -1;
        else
            return max(leftHeight,rightHeight)+1;
    }

public boolean isBalanced(TreeNode root) {
    if (root == null) return true;

    int left = getHeight(root.left);
    int right = getHeight(root.right);
    if (Math.abs(left - right) > 1) return false;

    return isBalanced(root.left) && isBalanced(root.right);
}

private int getHeight(TreeNode n) {
    if (n == null) return 0;

    return Math.max(getHeight(n.left), getHeight(n.right)) + 1;
}