首页 > 代码库 > 判断二叉树是否平衡

判断二叉树是否平衡

2024-07-11 21:54:10   227人阅读

题目：输入一棵二叉树的根结点，判断该树是不是平衡二叉树。如果某二叉树中任意结点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。
注：这里不考虑该二叉树是否是二叉排序树
解决要点：
1.后序遍历二叉树；
2.递归。

核心算法：

bool isBalanced(pTree pT,int *depth)
{
	if(!pT)//参数判断
	{
		*depth = 0;
		return true;
	}
	//后序遍历
	int left,right;
	if(isBalanced(pT->lChild,&left) && isBalanced(pT->rChild,&right))
	{
		int differ = left-right;
		if(differ >= -1 && differ <= 1)
		{        //记录深度
			*depth = (left > right) ? left+1 : right+1;
			return true;
		}
	}
	return false;
}
bool isBalanced(pTree root)//传入二叉树根节点
{
	int depth = 0;
	return isBalanced(root,&depth);
}

完整程序：

/*********************************
判断二叉树是否是平衡二叉树
by Rowandjj
2014/7/13
*********************************/
#include<iostream>
using namespace std;
typedef struct _NODE_
{
	int data;
	struct _NODE_ *lChild;
	struct _NODE_ *rChild;
}TreeNode,*pTree;
void Create(pTree *pT)
{
	int e;
	cin>>e;
	if(e != -1)
	{
		*pT = (TreeNode*)malloc(sizeof(TreeNode));
		if(!pT)
		{
			exit(-1);
		}
		(*pT)->data = http://www.mamicode.com/e;>


联系
我们