输入一棵二叉树的根节点,判断该树是不是平衡二叉树。
如果某二叉树中任意节点的左右子树的深度相差不超过1,那么它就是一棵平衡二叉树。
后序遍历二叉树,由底向上返回某一子树的深度,并判断是否某一子树是否是平衡树,只要任意子树不是平衡树,则整棵数都不是平衡树:
- 当节点的左右子树的深度差 < 2 ,则返回子树的深度,即:max(left_hight,right_hight)+1 。
- 当节点的左右子树的深度差 > 2,则返回-1,说明不是平衡树。
- 递归终止条件:root == NULL ,说明越过叶子节点,返回0 ;左右子树返回-1,说明不是二叉树,直接返回-1,没有必要再判断其他子树,这就是所谓的剪枝。
int max(int a,int b)
{
return a > b ? a:b ;
}
int recur(struct TreeNode* root)
{
int left_hight = 0;
int right_hight = 0;
if(root == NULL)
{
return 0;
}
left_hight = recur(root->left);
if(left_hight == -1)
{
return -1;
}
right_hight = recur(root->right);
if(right_hight == -1)
{
return -1;
}
return abs(left_hight - right_hight) < 2 ? (max(left_hight,right_hight)+1) : -1;
}
bool isBalanced(struct TreeNode* root){
if(recur(root) != -1)
{
return true;
}
else
{
return false;
}
}
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)