题目描述
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
题目解析
结合 重构二叉树题目
两道题基本一致，都是递归左右子树。
难点：在于思考清楚 左右子树的入口（左子树的范围，右子树的范围）
对于一次递归中的思路是：
先从一棵树的最左侧开始，若都小于该树的root 就向右滑动，直到遇到第一个比root大的值（左子树都应该< root）
然后再从第一个大的值开始，继续向右遍历（右子树都应该>root），若出现 小于的情况 则直接判false；
BST的后序序列的合法序列是：对于一个序列S，最后一个元素是x （也就是根），如果去掉最后一个元素的序列为T，那么T满足：T可以分成两段，前一段（左子树）小于x，后一段（右子树）大于x，且这两段（子树）都是合法的后序序列。完美的递归定义 。
题解
public boolean VerifySquenceOfBST(int [] sequence) {
int n = sequence.length;
if(n <= 0 || sequence == null ) return false;
return helper(sequence,0,n-1);
}
public boolean helper(int []sequence,int lo ,int hi){
// 递归出口 当lo == hi 时候表示当前节点即自己为根
// lo > hi 时候 表示出现null 节点
if (lo >= hi ) return true;
int root = sequence[hi];
int i = lo;
while (i < hi){
if (sequence[i] > root) break;
i++;
}
int j = i;
while (j < hi){
if (sequence[j] < root) return false;
j++;
}
// 划清左右子树范围，递归左右子树
return helper(sequence,lo,i-1) && helper(sequence,i,hi-1);
}
