后序遍歷求解判斷一顆二叉樹是否為平衡二叉樹

題目：輸入一棵二叉樹的根結(jié)點，判斷該樹是不是平衡二叉樹。如果某二叉樹中任意結(jié)點的左右子樹的深度相差不超過1，那么它就是一棵平衡二叉樹。

有了求二叉樹的深度的經(jīng)驗之后再解決這個問題，我們很容易就能想到一個思路：在遍歷樹的每個結(jié)點的時候，調(diào)用函數(shù)TreeDepth得到它的左右子樹的深度。如果每個結(jié)點的左右子樹的深度相差都不超過1，按照定義它就是一棵平衡的二叉樹。這種思路對應(yīng)的代碼如下：

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);
}

上面的代碼固然簡潔，但我們也要注意到由于一個節(jié)點會被重復(fù)遍歷多次，這種思路的時間效率不高。例如在函數(shù)IsBalance中輸入上圖中的二叉樹，首先判斷根結(jié)點（值為1的結(jié)點）的左右子樹是不是平衡結(jié)點。此時我們將往函數(shù)TreeDepth輸入左子樹根結(jié)點（值為2的結(jié)點），需要遍歷結(jié)點4、5、7。接下來判斷以值為2的結(jié)點為根結(jié)點的子樹是不是平衡樹的時候，仍然會遍歷結(jié)點4、5、7。毫無疑問，重復(fù)遍歷同一個結(jié)點會影響性能。接下來我們尋找不需要重復(fù)遍歷的算法。

如果我們用后序遍歷的方式遍歷二叉樹的每一個結(jié)點，在遍歷到一個結(jié)點之前我們已經(jīng)遍歷了它的左右子樹。只要在遍歷每個結(jié)點的時候記錄它的深度（某一結(jié)點的深度等于它到葉節(jié)點的路徑的長度），我們就可以一邊遍歷一邊判斷每個結(jié)點是不是平衡的。

#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;
}

在上面的代碼中，我們用后序遍歷的方式遍歷整棵二叉樹。在遍歷某結(jié)點的左右子結(jié)點之后，我們可以根據(jù)它的左右子結(jié)點的深度判斷它是不是平衡的，并得到當前結(jié)點的深度。當最后遍歷到樹的根結(jié)點的時候，也就判斷了整棵二叉樹是不是平衡二叉樹了。