后序遍历求解判断一颗二叉树是否为平衡二叉树

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

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