O(N) Simple Cpp Solution


#1

//In pair class first stores the height and second stores if it is a Balance Tree or Not(0 and 1 only)
pair<int,int> isbalanced(TreeNode* A){
if(A == NULL){
pair<int,int> ans;
ans.first = 0;
ans.second = 1;
return ans;
}
pair<int,int> leftAns = isbalanced(A->left);
pair<int,int> rightAns = isbalanced(A->right);
int leftHeight = leftAns.first;
int rightHeight = rightAns.first;
int height = 1 + max(leftHeight,rightHeight);
int answer = abs(leftHeight-rightHeight) <=1 && leftAns.second
&& rightAns.second;
pair<int,int> output;
output.first = height;
output.second = answer;
return output;
}
int Solution::isBalanced(TreeNode* A) {
if(A == NULL || (A->left == NULL && A->right == NULL)) return 1;
pair<int,int> answer = isbalanced(A);
return answer.second;
}