Cacher is the code snippet organizer for pro developers

// solution 1, straighforward, but need more recursions. Need O(N) space, N is the number of tree nodes
bool isBalanced(TreeNode *root) {
    if(!root) return true;
    if(!root->left && !root->right) return true;
    int h1 = get_height(root->left), h2 = get_height(root->right);
    return abs(h1 - h2) <= 1 && isBalanced(root->left) && isBalanced(root->right);
}
int get_height(TreeNode *root) {
    if(!root) return 0;
    if(!root->left && !root->right) return 1;
    int h1 = get_height(root->left), h2 = get_height(root->right);
    return h1 > h2 ? h1 + 1 : h2 + 1;
}

// solution 2, early termination. Much faster! Need O(h) space, where h is tree height
bool isBalanced(TreeNode *root) {
    return get_height2(root) != -1;
}

int get_height2(TreeNode *r) {
    if(!r) return 0;
    int h1 = get_height2(r->left);
    if(h1 == -1) return -1;
    int h2 = get_height2(r->right);
    if(h2 == -1) return -1;
    if(abs(h1 - h2) > 1) return -1;
    return max(h1, h2) + 1;
}