1.题目描述

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则返回 true ,否则返回 false 。假设输入的数组的任意两个数字都互不相同。

数据范围： 节点数量 0 \le n \le 10000≤n≤1000 ，节点上的值满足 1 \le val \le 10^{5}1≤val≤105 ，保证节点上的值各不相同
要求：空间复杂度 O(n)O(n) ，时间时间复杂度 O(n^2)O(n2)

提示：

1.二叉搜索树是指父亲节点大于左孩子节点，但是小于右孩子节点。

2.该题我们约定空树不是二叉搜索树

3.后序遍历是指按照 “左子树-右子树-根节点” 的顺序遍历

4.参考下面的二叉搜索树，示例 1

 2.算法分析

题目中要求判断数组是否为  ：二叉树搜索树的后续遍历序列。

①数组中的最后一个结点是二叉搜索树的根节点。

②二叉搜索树规则：根结点的值大于左孩子结点的值，根结点的值大于右孩子结点的值。

③根据根节点找到数组中左右孩子的分界点

④根据递归处理左孩子的所有结点和右孩子的所有结点   

代码如下：

3.代码实现

/*
    二叉搜索树，根结点的值始终大于左孩子结点的值，根结点的值始终大于右孩子结点的值
    在左右孩子结点情况是一样的。
    本题的重点是找到根结点
    后续遍历：左--右--中、
*/
public class Solution {
    public boolean VerifySquenceOfBST(int [] sequence) {
        if(sequence == null || sequence.length == 0){
            return false;
        }
        return Verify(sequence,0,sequence.length - 1);
    }
    public boolean Verify(int[] array,int start,int end){
        // 递归结束标志    
        if(start > end){
            return true;
        }
        int tempIndex = start;
        while(array[tempIndex] < array[end] ){
            tempIndex++;
        }
        // 找到中间值
        int midIndex = tempIndex;
        while(array[midIndex] > array[end]){
            midIndex++;
        }
        // 当 midIndex == end时候 
        return (midIndex == end) && Verify(array,start,midIndex - 1) && Verify(array,midIndex,end -1);
    }    
    
}