首页 > 代码库 > 推断二叉树是否平衡
推断二叉树是否平衡
题目：输入一棵二叉树的根结点，推断该树是不是平衡二叉树。假设某二叉树中随意结点的左右子树的深度相差不超过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;>
推断二叉树是否平衡
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。