【原题】
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
【思路】
后续遍历那么最后一个是根结点，由二叉搜索树的特征可以知道，可以把最后一个结点作为划分结点，找第一个大于根结点的左边作为左子树，右边（包含此元素）作为右子树。判断左右子树里面的元素是否满足左<根<右的关系，再依次递归判断左右子树。
public class Solution {
public boolean VerifySquenceOfBSTCore(int [] sequence, int start, int end){
if(end-start<=1) return true;//当只有一个元素或者为空时，肯定满足条件
int root=sequence[end-1];
int splitIndex=start;
for(;splitIndex<end-1;splitIndex++)
if(sequence[splitIndex]>root)//找左右子树的划分点
break;
for(int i=splitIndex;i<end-1;i++)
if(sequence[i]<root) //再找到划分点的情况下，若右子树还有元素小于根结点，说明不满足二叉搜索树的条件，返回false
return false;
boolean left=true;
//递归判断左右子树是不是二叉搜索树
left=VerifySquenceOfBSTCore(sequence,start,splitIndex);
boolean right=true;
right=VerifySquenceOfBSTCore(sequence,splitIndex,end-1);
return left&&right;
}
public boolean VerifySquenceOfBST(int [] sequence) {
if(sequence==null||sequence.length<=0) return false;
return VerifySquenceOfBSTCore(sequence, 0,sequence.length);
}
}