題目：輸入一棵二叉樹的根結點，判斷該樹是不是平衡二叉樹。如果某二叉樹中任意結點的左右子樹的深度相差不超過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;
}
在上面的代碼中，我們用後序遍歷的方式遍歷整棵二叉樹。在遍歷某結點的左右子結點之後，我們可以根據它的左右子結點的深度判斷它是不是平衡的，並得到當前結點的深度。當最後遍歷到樹的根結點的時候，也就判斷了整棵二叉樹是不是平衡二叉樹了。
