题目描述：
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则返回true,否则返回false。假设输入的数组的任意两个数字都互不相同。（ps：我们约定空树不是二叉搜素树）
示例：
输入：
[4,8,6,12,16,14,10]
返回：
TRUE
思路：
- 首先，对于后序遍历，数组的最后一位一定是该二叉树的根节点；
- 除去最后一位，数组中剩下的数字可以分为两部分：
-- 左子树中的所有数字都比根节点小
-- 右子树中的所有数字都比根节点大 - 递归判断
code：
public class solution{
public boolean VerifySquenceOfBST(int [] sequence) {
if(sequence==null||sequence.length==0){
return false;
}
return isBigger(sequence,0,sequence.length-1);
}
public boolean isBigger(int[] s, int start, int end){
// 递归终止条件：
// 已经遍历到最后，此时start = end
if(start >= end){return true;}
// 寻找第一个比s[end]大的数
int index = 0;
while(index != end){
if(s[index] > s[end]){break;}
else{index++};
}
//在0-index之间的所有数都比s[end]小
for(int i=start;i<index;i++){if(s[i]>s[end])return false;}
//在index-end-1之间所有数都比s[end]大
for(int i=index;i<end;i++){if(s[i]<s[end])return false;}
return isBigger(s,start,index-1) && isBigger(s,index,end-1);
}
}
特别注意：递归终止的条件是 start >=end而不是 start == end！！！
如：
[4,5]
第一轮： start = 0,end = 1, index =1;
第二轮: start = 0,end =index-1= 0; start =index=1, end=end-1=0(此时出现了start > end);
