题目：输入一棵二叉树的根结点，判断该树是不是平衡二叉树。如果某二叉树中任意结点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。


有了求二叉树的深度的经验之后再解决这个问题，我们很容易就能想到一个思路：在遍历树的每个结点的时候，调用函数TreeDepth得到它的左右子树的深度。如果每个结点的左右子树的深度相差都不超过1，按照定义它就是一棵平衡的二叉树。这种思路对应的代码如下：

boolIsBalanced(BinaryTreeNode*pRoot){if(pRoot==NULL)returntrue;intleft=TreeDepth(pRoot->m_pLeft);intright=TreeDepth(pRoot->m_pRight);intdiff=left-right;if(diff>1||diff<-1)returnfalse;returnIsBalanced(pRoot->m_pLeft)&&IsBalanced(pRoot->m_pRight);}


上面的代码固然简洁，但我们也要注意到由于一个节点会被重复遍历多次，这种思路的时间效率不高。例如在函数IsBalance中输入上图中的二叉树，首先判断根结点（值为1的结点）的左右子树是不是平衡结点。此时我们将往函数TreeDepth输入左子树根结点（值为2的结点），需要遍历结点4、5、7。接下来判断以值为2的结点为根结点的子树是不是平衡树的时候，仍然会遍历结点4、5、7。毫无疑问，重复遍历同一个结点会影响性能。接下来我们寻找不需要重复遍历的算法。

如果我们用后序遍历的方式遍历二叉树的每一个结点，在遍历到一个结点之前我们已经遍历了它的左右子树。只要在遍历每个结点的时候记录它的深度（某一结点的深度等于它到叶节点的路径的长度），我们就可以一边遍历一边判断每个结点是不是平衡的。

#include<iostream>#include<stack>usingnamespacestd;structBinaryTreeNode{intdata;BinaryTreeNode*left;BinaryTreeNode*right;BinaryTreeNode(intx):data(x),left(NULL),right(NULL){}};classBinaryTree{protected:BinaryTreeNode*_root;BinaryTreeNode*_CreateBinaryTree(int*arr,int&index,intsize){BinaryTreeNode*root=NULL;if(index<size&&arr[index]!='#'){root=newBinaryTreeNode(arr[index]);root->left=_CreateBinaryTree(arr,++index,size);root->right=_CreateBinaryTree(arr,++index,size);}returnroot;}public:BinaryTree():_root(NULL){}BinaryTree(int*arr,intsize){intindex=0;_root=_CreateBinaryTree(arr,index,size);}boolIsBalance(){intdepth=0;return_IsBalance(_root,depth);}intHeight(){return_Height(_root);}voidPreOrder_Non(){if(_root==NULL)return;BinaryTreeNode*cur=_root;stack<BinaryTreeNode*>s;s.push(_root);while(!s.empty()){cur=s.top();printf("%d",cur->data);s.pop();if(cur->right)s.push(cur->right);if(cur->left)s.push(cur->left);}cout<<endl;}protected:int_Height(BinaryTreeNode*root){if(root==NULL)return0;intleft=_Height(root->left);intright=_Height(root->right);returnleft>right?left+1:right+1;}bool_IsBalance(BinaryTreeNode*root,int&depth){if(root==NULL)returntrue;intleft,right;if(_IsBalance(root->left,left)&&_IsBalance(root->right,right)){intdif=left-right;if(dif<=1&&dif>=-1){depth=left>right?left+1:right+1;returntrue;}}returnfalse;}};intmain(){inta[]={1,2,3,'#','#','#'};BinaryTreet(a,sizeof(a)/sizeof(a[0]));t.PreOrder_Non();cout<<t.IsBalance()<<endl;system("pause");return0;}


在上面的代码中，我们用后序遍历的方式遍历整棵二叉树。在遍历某结点的左右子结点之后，我们可以根据它的左右子结点的深度判断它是不是平衡的，并得到当前结点的深度。当最后遍历到树的根结点的时候，也就判断了整棵二叉树是不是平衡二叉树了。