学步园

题目：输入一个整数数组，判断该数组是不是某二元查找树的后序遍历的结果。

如果是返回true，否则返回false。

例如输入5、7、6、9、11、10、8，由于这一整数序列是如下树的后序遍历结果.

    　　8

 　　  / \

 　　6   10

　　/ \    / \

　 5  7 9 11

因此返回true。

如果输入7、4、6、5，没有哪棵树的后序遍历的结果是这个序列，因此返回false。

5、7、6、9、11、10、8

分析：按照二元查找树后续遍历的性质：最后一个节点是根（8），从一个元素开始与根比较，找到第一个大于根的值，记录下该位置i,位置i之前的是根的左子树，之后的是根的右子树，故右子树的值需要均大于根的值，否则，就不是二元查找树的后序遍历结果，然后采用递归处理之。（按性质判断即可，不需要构建一个二元查找树）。

bool Posorder(int a[], int left, int right)
{
	if(a==NULL || left<0 || right <left)
		return false;

	if(left>=right)
		return true;

	int length = right-left+1;

	int i=0;
	int root = a[right];

	for(i=left; i<left+length-1; i++)   //找到第一个大于根的值,注意i=left,防止右子树的时候出错，length-1不跟根比较
	{
		if(a[i]>root)
			break;
	}

	int j=i;
	for(j=i; j<left+length-1; j++)   //如果右子树的值大于根，则不符合二元查找树的性质
	{
		if(a[j]<root)
			return false;
	}

	bool flagLeft = true;
	flagLeft = Posorder(a, left, i-1);   //递归：如何确定返回值

	bool flagRight = true;
	flagRight = Posorder(a, i, right-1);

	return (flagLeft && flagRight);
}