/**输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。
* 如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
* 一开始不是很明白题目意思，以为是让我后序遍历某棵二叉树
* 后来搞明白了。
* 二叉搜索树就像是二分查找里面的，左子树的所有元素都小于根节点，右子树的所有元素都大于根节点。
*例如{5,7,6,9,11,10,8},8是根节点，则我们可以从头开始找比8大的节点，就可以找到左右子树的分界了
*这时我们找到了9，然后我们在验证左子树(5,7,6)是否都小于根节点8，验证右子树(9,11,10)是否都大于根节点8.
*然后又继续验证左子树和右子树内部是否符合，于是可以用到递归。
*例如{7,4,5,6},6是根节点，我们可以发现这棵树没有左子树，于是我们验证(7,4,5)是否都大于根节点6
*但是此时我们发现4并不大于根节点，说明不符合。
*测试用例：
*1.功能测试：左右子树都有的：{5,7,6,9,11,10,8},只有右子树的{7,4,5,6},只有左子树的{5,4,3,2,1}
*2.边界测试:给定数组为空或者长度为0的。
* @author admin
*
*/
public class VerifySequenceOfABST {
public static boolean VerifySquenceOfBST(int [] sequence) {
if(sequence==null||sequence.length==0) {
return false;
}
return verifySequence(0,sequence.length-2,sequence[sequence.length-1],sequence);
}
public static boolean verifySequence(int start,int end,int root,int[] sequence) {
if(end<=start) {//当end<start时，说明不需要验证了，返回true
return true;
}
int i=start;
//找出左右子树的分界
for(;i<=end;i++) {
if(sequence[i]>root) {
break;
}
}
boolean left=true;
//验证左子树是否都小于根
for(int j=start;j<=i-1&&left;j++) {
if(sequence[j]>root) {
left=false;
}
}
boolean right=true;
//验证右子树是否都大于根
for(int j=i;j<=end&&right;j++) {
if(sequence[j]<root) {
right=false;
}
}
if(i>start) {//如果i>start，则继续往下验证，因为有可能只有右子树
left=left&&verifySequence(start,i-2,sequence[i-1],sequence);
}
if(i<end) {//如果i<end，则继续往下验证，因为有可能只有左子树
right=right&&verifySequence(i,end-1,sequence[end],sequence);
}
return left&&right;
}
public static void main(String[] args) {
int[] sequence={5,4,3,2,1};
System.out.println(VerifySquenceOfBST(sequence));
}
}