如何判断二叉树是否平衡

如何判断二叉树是否平衡2015-09-22题目：输入一棵二叉树的根结点，判断该树是不是平衡二叉树。如果某二叉树中任意结点的左右子树的深度相差不超过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;}

作者：csdn博客 RowandJJ