Given a binary tree, determine if it is height-balanced.
For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees ofevery node never differ by more than 1.Solution:
int GetHeight(TreeNode *root)
{
if(!root)
return 0;
int leftheight = GetHeight(root->left);
int rightheight = GetHeight(root->right);
if(leftheight-rightheight>1||leftheight-rightheight<-1||rightheight ==-1||leftheight ==-1)
return -1;
return leftheight>rightheight?leftheight+1:rightheight+1;
}
bool isBalanced(TreeNode *root) {
if(!root)
return true;
int result = GetHeight(root);
if(result==-1)
return false;
else
return true;
}
No comments:
Post a Comment