题目：输入一棵二叉树的根结点，判断该树是不是平衡二叉树。如果某二叉树中任意结点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。
有了求二叉树的深度的经验之后再解决这个问题，我们很容易就能想到一个思路：在遍历树的每个结点的时候，调用函数TreeDepth得到它的左右子树的深度。如果每个结点的左右子树的深度相差都不超过1，按照定义它就是一棵平衡的二叉树。这种思路对应的代码如下：
bool IsBalanced(BinaryTreeNode* pRoot)
{
if(pRoot == NULL)
return true;
int left = TreeDepth(pRoot->m_pLeft);
int right = TreeDepth(pRoot->m_pRight);
int diff = left - right;
if(diff > 1 || diff < -1)
return false;
return IsBalanced(pRoot->m_pLeft) && IsBalanced(pRoot->m_pRight);
}
上面的代码固然简洁，但我们也要注意到由于一个节点会被重复遍历多次，这种思路的时间效率不高。例如在函数IsBalance中输入上图中的二叉树，首先判断根结点（值为1的结点）的左右子树是不是平衡结点。此时我们将往函数TreeDepth输入左子树根结点（值为2的结点），需要遍历结点4、5、7。接下来判断以值为2的结点为根结点的子树是不是平衡树的时候，仍然会遍历结点4、5、7。毫无疑问，重复遍历同一个结点会影响性能。接下来我们寻找不需要重复遍历的算法。
如果我们用后序遍历的方式遍历二叉树的每一个结点，在遍历到一个结点之前我们已经遍历了它的左右子树。只要在遍历每个结点的时候记录它的深度（某一结点的深度等于它到叶节点的路径的长度），我们就可以一边遍历一边判断每个结点是不是平衡的。
#include<iostream>
#include<stack>
using namespace std;
struct BinaryTreeNode
{
int data;
BinaryTreeNode* left;
BinaryTreeNode* right;
BinaryTreeNode(int x)
:data(x)
, left(NULL)
, right(NULL)
{}
};
class BinaryTree
{
protected:
BinaryTreeNode* _root;
BinaryTreeNode* _CreateBinaryTree(int* arr, int& index, int size)
{
BinaryTreeNode* root = NULL;
if (index < size&&arr[index] != '#')
{
root = new BinaryTreeNode(arr[index]);
root->left = _CreateBinaryTree(arr, ++index, size);
root->right = _CreateBinaryTree(arr, ++index, size);
}
return root;
}
public:
BinaryTree()
:_root(NULL)
{}
BinaryTree(int *arr, int size)
{
int index = 0;
_root = _CreateBinaryTree(arr, index, size);
}
bool IsBalance()
{
int depth = 0;
return _IsBalance(_root, depth);
}
int Height()
{
return _Height(_root);
}
void PreOrder_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)
return 0;
int left = _Height(root->left);
int right = _Height(root->right);
return left > right ? left + 1 : right + 1;
}
bool _IsBalance(BinaryTreeNode* root, int& depth)
{
if (root == NULL)
return true;
int left, right;
if (_IsBalance(root->left, left) && _IsBalance(root->right, right))
{
int dif = left - right;
if (dif <= 1 && dif >= -1)
{
depth = left > right ? left + 1 : right + 1;
return true;
}
}
return false;
}
};
int main()
{
int a[] = { 1,2,3,'#','#','#'};
BinaryTree t(a,sizeof(a)/sizeof(a[0]));
t.PreOrder_Non();
cout<<t.IsBalance()<<endl;
system("pause");
return 0;
}