class Solution {
    public:
        bool isBalanced(TreeNode* root) {
            if(root == NULL)
                return true;
            if(root->left == NULL&&root->right == NULL)
                return true;
            if(abs(depth(root->left)-depth(root->right))>1)
                return false;
            return isBalanced(root->left)&&isBalanced(root->right);
        }
        int depth(TreeNode* root){
            if(root == NULL)
                return 0;
            return max(1+depth(root->left),1+depth(root->right));
        }
    };

class Solution {
public:
    bool isBalanced(TreeNode* root) {
        // write code here
        int high=0;
        return isBalance1(root,high);
    }
    bool isBalance1(TreeNode* root,int &high)
    {
        if(root==NULL)
        {
            high=0;
            return true;
        }
        int lhigh,rhigh;
        if(!isBalance1(root->left,lhigh)||!isBalance1(root->right,rhigh))
            return false;
        if(lhigh-rhigh>1||lhigh-rhigh<-1)
            return false;
        high=(lhigh>=rhigh?lhigh:rhigh)+1;
        return true;
    }
};