推断二叉树是否平衡


题目:输入一棵二叉树的根结点,推断该树是不是平衡二叉树。假设某二叉树中随意结点的左右子树的深度相差不超过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 = e;
		(*pT)->lChild = NULL;
		(*pT)->rChild = NULL;
		Create(&(*pT)->lChild);
		Create(&(*pT)->rChild);
	}
}
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);
}
void travel(pTree pT)
{
	if(pT != NULL)
	{
		travel(pT->lChild);
		travel(pT->rChild);
		cout<<pT->data<<" ";
	}
}
int main()
{
	pTree pT;
	Create(&pT);
	travel(pT);
	cout<<endl;
	cout<<isBalanced(pT);
	return 0;
}




优质内容筛选与推荐>>
1、ajax评论
2、JavaScript数值转换总结
3、Linux下查看nginx的安装路径
4、<cocos2d-x for window phone>一个简单的打地鼠游戏
5、织梦Dedecms中万能标签loop不能输入URL的解决方法


长按二维码向我转账

受苹果公司新规定影响,微信 iOS 版的赞赏功能被关闭,可通过二维码转账支持公众号。

    阅读
    好看
    已推荐到看一看
    你的朋友可以在“发现”-“看一看”看到你认为好看的文章。
    已取消,“好看”想法已同步删除
    已推荐到看一看 和朋友分享想法
    最多200字,当前共 发送

    已发送

    朋友将在看一看看到

    确定
    分享你的想法...
    取消

    分享想法到看一看

    确定
    最多200字,当前共

    发送中

    网络异常,请稍后重试

    微信扫一扫
    关注该公众号





    联系我们

    欢迎来到TinyMind。

    关于TinyMind的内容或商务合作、网站建议,举报不良信息等均可联系我们。

    TinyMind客服邮箱:support@tinymind.net.cn