Leecode33：二叉搜索树的后续遍历序列

依据：

1：因为是后续遍历，那么最后的数字代表的节点一定是根节点。

2：左子树中的元素大小一定比根节点点小，右子树的元素大小一定比根节点大。

思路：

1：用递归，判断每一个子树是否满足1、2；

2：确定一个子树区间：[i,j]，从j->i遍历，寻找第一个小于序号j元素的元素，元素即为左子树根节点，右子树根节点序号围殴为j-1

代码：

class Solution {
public:
	int GetLower(vector<int>& p, int L, int R) {
		for (int i = R - 1; i >= L; i--) {
			if (p[i] < p[R]) {
				for (int j = L; j <= i; j++) {
					if (p[j] > p[R]) 
						return -2;
				}
				return i;
			}
		}
		return -1;
	}
	int GetUper(vector<int>& p, int L, int R) {
		for (int i = R - 1; i >= L; i--) {
			if (p[i] > p[R]) {
				for (int j = L; j <= i; j++) {
					if (p[j] < p[R]) 
						return -2;
				}
				return i;
			}
		}
		return -1;
	}
	bool Check(vector<int>& p, int L, int R) {
		if (L == R) return true;
		int Min_Pos = GetLower(p, L, R);
		if (Min_Pos == -2 ){
			return false;
		}
		int Max_Pos = GetUper(p, Min_Pos != -1 ? Min_Pos + 1 : L, R);
 
		if (Max_Pos == -2) {
			return false;
		}
 
		if (Max_Pos != R - 1 && Max_Pos != -1)
			return false;
 
		if (Min_Pos == -1|| Max_Pos == -1) {
			return Check(p, L, R - 1);
		}
		return Check(p, L, Min_Pos) && Check(p, Min_Pos + 1, Max_Pos);
 
	}
	bool verifyPostorder(vector<int>& postorder) {
        if(postorder.size()==0) return 1;
		return Check(postorder, 0, postorder.size() - 1);
	}
};