Easy recursive solution c++


#1

int height(TreeNode* A){
if(A==NULL){
return 0;
}
return 1+max(height(A->left),height(A->right));
}
int Solution::isBalanced(TreeNode* A) {
if(A==NULL){
return 1;
}
int h1= height(A->left);
int h2= height(A->right);
if(abs(h1-h2)<=1){
int a=isBalanced(A->left);
int b=isBalanced(A->right);
return a && b;
}
return 0;
}


#2

It is very inefficient approach. To make your algorithm efficient, you must use memoization. If you don’t want to use memoization, you can do recursion like this…
int height(TreeNode* A)
{
if(!A) return 0;
int h1 = height(A->left), h2 = height(A->right);
if(h1==-1 || h2==-1) return -1;
if(abs(h1-h2)<=1)
{
return max(h1,h2)+1;
}
else
{
return -1;
}
}
int Solution::isBalanced(TreeNode* A) {
if(!A) return 1;
if(height(A)>=0) return 1;
else return 0;
}