【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;
	}
}



相关文章
|
10月前
|
【C/C++ 数据结构 】二叉树基本性质:对于任何一颗二叉树T,若其终端结点为n0 ,那么度数为2的结点数为n2。则n0=n2+1...
【C/C++ 数据结构 】二叉树基本性质:对于任何一颗二叉树T,若其终端结点为n0 ,那么度数为2的结点数为n2。则n0=n2+1...
119 0
|
9月前
|
数据结构和算法学习记录——层序遍历(层次遍历)、二叉树遍历的应用(输出二叉树中的叶节点、求二叉树的高度、二元运算表达式树及其遍历、由两种遍历序列确定二叉树)
数据结构和算法学习记录——层序遍历(层次遍历)、二叉树遍历的应用(输出二叉树中的叶节点、求二叉树的高度、二元运算表达式树及其遍历、由两种遍历序列确定二叉树)
97 0
初阶数据结构之---二叉树链式结构(二叉树的构建,二叉树的前序,中序,后序和层序遍历,计算二叉树结点个数,第k层结点个数,叶子结点个数,判断是否为完全二叉树)
初阶数据结构之---二叉树链式结构(二叉树的构建,二叉树的前序,中序,后序和层序遍历,计算二叉树结点个数,第k层结点个数,叶子结点个数,判断是否为完全二叉树)
【算法】二叉排序树:创建二叉树,并以中序遍历输出
【算法】二叉排序树:创建二叉树,并以中序遍历输出
236 0
每日三题-验证二叉搜索树、二叉树的直径、把二叉搜索树转换为累加树
每日三题-验证二叉搜索树、二叉树的直径、把二叉搜索树转换为累加树验证二叉搜索树验证二叉搜索树v
72 2
每日三题-验证二叉搜索树、二叉树的直径、把二叉搜索树转换为累加树
每日三题-二叉树的层序遍历、二叉树的中序遍历、最小覆盖子串
每日三题 二叉树的层序遍历 二叉树的中序遍历 最小覆盖子串
114 1
每日三题-二叉树的层序遍历、二叉树的中序遍历、最小覆盖子串
二叉树的层序遍历、二叉树叶节点输出算法、求二叉树的高度、层序创建一棵二叉树
二叉树的层序遍历、二叉树叶节点输出算法、求二叉树的高度、层序创建一棵二叉树
判断一棵树是不是完全二叉树
判断一棵树是不是完全二叉树
输入一棵二叉树,判断该二叉树是否是平衡二叉树(Java版)/输入一棵二叉树,求该树的深度。从根结点到叶结点依次经过的结点(含根、叶结点)形成树的一条路径,最长路径的长度为树的深度。(Java版)
输入一棵二叉树,判断该二叉树是否是平衡二叉树(Java版)/输入一棵二叉树,求该树的深度。从根结点到叶结点依次经过的结点(含根、叶结点)形成树的一条路径,最长路径的长度为树的深度。(Java版)
149 0
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等