输入一棵二叉树,判断该二叉树是否是平衡二叉树。
平衡二叉树是这样定义的: 平衡二叉树(Balanced Binary Tree)又被称为AVL树,具有以下性质:它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。 所以算法分为两部分:计算左右子树高度(即为深度),和左右子树是否仍为AVL树
对每个节点,计算它的左右子树的深度差的平方(因为不知道哪一个子树深度比较大,使用平方),如果深度差的平方大于1,则该树不平衡,返回false 如果深度差的平方小于等于1,递归查看它的左右子树是否是AVL树
class Solution {
public:
bool IsBalanced_Solution(TreeNode* pRoot) {
if(pRoot==NULL) return true;
//求其左右子树的深度差
int depthLeft=TreeDepth(pRoot->left);
int depthRight=TreeDepth(pRoot->right);
int diff=(depthLeft-depthRight);
int diff2=diff*diff;
//若左右子树深度差平方大于1,立即返回false
if(diff2>1){
return false;
}
//若左右子树的深度差平方小于等于1,递归查看其子树
else{
return IsBalanced_Solution(pRoot->left)&&IsBalanced_Solution(pRoot->right);
}
}
int TreeDepth(TreeNode* pRoot)
{
if(pRoot!=NULL){
int depthL=TreeDepth(pRoot->left);
int depthR=TreeDepth(pRoot->right);
int max=depthL>depthR?depthL:depthR;
return max+1;
}else{
return 0;
}
}
};