【2】输入一颗二叉树判断是不是平衡二叉树-阿里云开发者社区

开发者社区> 陈国林> 正文

【2】输入一颗二叉树判断是不是平衡二叉树

简介: 题目:输入一颗二叉树的根结点,判断该二叉树是不是平衡二叉树。平衡二叉树是满足所有结点的左右子树的高度差不超过1的二叉树 方案一:遍历数组的每一个结点,对每一个结点求它的左右子树的高度并进行判断。
+关注继续查看

题目:输入一颗二叉树的根结点,判断该二叉树是不是平衡二叉树。平衡二叉树是满足所有结点的左右子树的高度差不超过1的二叉树


方案一:遍历数组的每一个结点,对每一个结点求它的左右子树的高度并进行判断。时间复杂度大于O(n),小于O(n^2)效率较低,因为有很多点需要重复访问。

//二叉树的结点
struct BinaryTreeNode{
     int m_value;
     BinaryTreeNode *m_lson;
     BinaryTreeNode *m_rson;
};

//求二叉树的深度
int GetDepth(BinaryTreeNode *root){
	if(root == NULL){
	   return 0;
	}
	int lsonDepth = GetDepth(root->m_lson);
	int rsonDepth = GetDepth(root->m_rson);
	return lsonDepth < rsonDepth ? (rsonDepth+1) : (lsonDepth+1);
}

//方案一对每个结点进行判断
bool IsBalanced(BinaryTreeNode *root){
	if(root == NULL){
	    return true;
	}
	int lsonDepth = GetDepth(root->m_lson);
	int rsonDepth = GetDepth(root->m_rson);
	int dis = lsonDepth-rsonDepth;
	if((dis <= 1) && (dis >= -1)){
		return IsBalanced(root->m_lson) && IsBalanced(root->m_rson);
	}
	else{
	    return false;
	}
} 


方案二:利用二叉树的后序遍历,对于先访问左右子树,然后对每个根结点进行判断,传入一个高度的参数即可。时间复杂度为O(n)。

//二叉树的结点
struct BinaryTreeNode{
     int m_value;
     BinaryTreeNode *m_lson;
     BinaryTreeNode *m_rson;
};

//后序遍历判断是不是平衡二叉树
bool IsBalanced(BinaryTreeNode *root, int *depth){
	if(root == NULL){
	    *depth = 0;
	    return true;
	}
	int lsonDepth = 0;
	int rsonDepth = 0;
	if(IsBalanced(root->m_lson, &lsonDepth) 
		&& IsBalanced(root->m_rson, &rsonDepth)){
	    int dis = lsonDepth-rsonDepth;
		if((dis >= -1) && (dis <= 1)){
		    *depth = 1+(lsonDepth < rsonDepth ? rsonDepth : lsonDepth);
		    return true;
		}
		else{
		    return false;
		}
	}
	else{
	    return false;
	}
}



版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
+关注
陈国林
曾任职于阿里巴巴,现就职于美图,专业搬砖100年~
723
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
《2021云上架构与运维峰会演讲合集》
立即下载
《零基础CSS入门教程》
立即下载
《零基础HTML入门教程》
立即下载