* 最近几天被推荐参加互联网+比赛，一直忙着团队前期工作。。拖更了。。 *
题目描述：

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。

实现如下：

//找规律
//      8
//  6      10
//5   7  9    11
//{5，7，6，9，11，10，8}
//最后一个为树的root
//{5，6，7}为左子树、{9，11，10}为右子树
//递归判断
//假定{7，4，6，5}
//7大于root，所以7之后的数为右子树，但又出现了比root小的数，所以次遍历结果false
class Solution 
{
public:
	//传入root下标和此子树最小元素的下标
	bool Verify(vector<int> sequence, int rootIndex, int minIndex)
	{
		if (minIndex - rootIndex >= 0) return true;//判断此子树是否为空或只有1个元素
		else
		{
			int leftIndex = minIndex;//保存左子树的root下标
			while (leftIndex < rootIndex && sequence[leftIndex] < sequence[rootIndex])//寻找第一个大于root值的元素的下标
			{
				++leftIndex;
			}
			int rightIndex = leftIndex;
			while (rightIndex < rootIndex)//判断右子树中是否有小于root的元素
			{
				if (sequence[rightIndex] < sequence[rootIndex])//若有直接return
					return false;
				++rightIndex;
			}
			return Verify(sequence, leftIndex - 1, minIndex) && Verify(sequence, rootIndex - 1, leftIndex);//对左子树和右子树继续递归
		}
	}

	bool VerifySquenceOfBST(vector<int> sequence) 
	{
		//统一使用下标
		int maxIndex = sequence.size() - 1;
		if (maxIndex < 0) return false;//防御性动作
		else if (maxIndex == 0) return true;//只有一个元素时直接return
		else
			return Verify(sequence, maxIndex, 0);//将此树的root和最小数的下标传入
	}
};