/**
 knakul853
 */
class Solution {
public:
    bool isBalanced(TreeNode* root) {

        if(!root)return 1;

        int lh = ht(root->left);
        int rh = ht(root->right);

        bool res = true;
        res&=abs(lh - rh)<=1;
        res&=isBalanced(root->left);
        res&=isBalanced(root->right);
         return res;



    }

    private:
    int ht(TreeNode* node)
    {
        if(!node)return 0;
        return 1+max(ht(node->left),ht(node->right));
    }
};

//https://leetcode.com/problems/balanced-binary-tree/discuss/35691/The-bottom-up-O(N)-solution-would-be-better
class solution {
public:
int dfsHeight (TreeNode *root) {
        if (root == NULL) return 0;

        int leftHeight = dfsHeight (root -> left);
        if (leftHeight == -1) return -1;
        int rightHeight = dfsHeight (root -> right);
        if (rightHeight == -1) return -1;

        if (abs(leftHeight - rightHeight) > 1)  return -1;
        return max (leftHeight, rightHeight) + 1;
    }
    bool isBalanced(TreeNode *root) {
        return dfsHeight (root) != -1;
    }
};