判断一棵二叉树是否是平衡二叉树
我们先来整理一下什么是平衡二叉树?
满足以下两点的就是平衡二叉树:
1.左右子树的高度差不能超过1
2.左右子树也是平衡二叉树
需要注意的是空树也是平衡二叉树
例如下面这棵树就不是平衡二叉树
因为对于B来说左右子树高度超过了1,所以它不是平衡二叉树。
方法一:
这样的话,如果是空树则是平衡二叉树,如果不是空树,我们就去判断左子树是不是平衡二叉树,判断的依据就是左右子树高度差不超过1,代码如下:
int IsBalance(BNode *root)
{
if (root == NULL)
{
return 1;
}
int isBalance = IsBalance(root->left);
if (isBalance == 0)
{
return 0;
}
int leftHight = GetHeight(root->left);
int rightHight = GetHeight(root->right);
int diff = leftHight - rightHight;
if (diff < -1 && diff>1)
{
return 0;
}
else {
return 1;
}
}
方法二:
通过上面的代码我们可以看出,递归的时候要遍历看是不是平衡,并且又要遍历高度,这样的话效率并不是很高,那么这时候就想,每次遍历的时候能不能直接将高度也返回呢?如下面的代码:
int IsBalance(BNode *root,int *pHeight)
{
if (root == NULL)
{
*pHeight = 0;
return 1;
}
int leftHeight;
int rightHeight;
int leftBalance = IsBalance(root->left, &leftHeight);
int rightBalance = IsBalance(root->right, &leftHeight);
*pHeight = MAX(leftHeight, rightHeight) + 1;
if (leftBalance == 0 || rightBalance == 0)
{
return 0;
}
int diff = leftHeight - rightHeight;
if (diff < -1 && diff>1)
{
return 0;
}
else {
return 1;
}
}