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

这里遇到的问题就是，传递的子数组怎么递归的传递下去，（Java基础不好，所以很多接口与方法都不熟悉）

看过答案之后，用的是Arrays的方法Arrays.copyOfRange(arrays, 1, 9);很神奇

还有就是左右两边子树判断的情况是不一样的，所以自己想的就很尴尬，不知道怎么处理

看了别人的答案之后，很神奇，先处理左边子树，在处理右边子树，然后再递归的进行左右子树内部的处理。

import java.util.Arrays;public class Solution {    public boolean VerifySquenceOfBST(int [] sequence) {        if(sequence.length == 0) return false;        int len = sequence.length;        int root = sequence[len - 1];        int i = 0;        for(; i < len - 1; i++){            if(root < sequence[i]) break;        }        int j = i;        for(; j < len - 1; j++){            if(root > sequence[j]) return false;        }        boolean leftIsBST = true;        if(i > 0){            leftIsBST = VerifySquenceOfBST(Arrays.copyOfRange(sequence, 0, i));        }        boolean rightIsBST = true;        if(j < len - 1){            rightIsBST = VerifySquenceOfBST(Arrays.copyOfRange(sequence, i, j));        }        return leftIsBST && rightIsBST;    }}

　　

 

下面这一种方式不是很理解

看的别人的 i 定义为一个右边子树的开始结点，但是想不明白为什么要遍历一遍数组，来找出root>sequence[j]的个数来作为i

 

import java.util.Arrays;public class Solution {    public boolean VerifySquenceOfBST(int [] sequence) {        if(sequence.length == 0) return false;        int len = sequence.length;        int root = sequence[len - 1];        int i = 0;        for(int j = 0; j < len - 1; j++){            if(root > sequence[j]) i++;        }        if(i == 0){            VerifySquenceOfBST(Arrays.copyOfRange(sequence, 0, len - 1));        }else{            for(int j = i; j < len - 1; j++){                if(root > sequence[j]) return false;            }            VerifySquenceOfBST(Arrays.copyOfRange(sequence, 0, i));            VerifySquenceOfBST(Arrays.copyOfRange(sequence, i, len - 1));        }        return true;    }}

　　

 重新写了一个不传递数组，直接传子数组的位置大小的

public class Solution {    public boolean VerifySquenceOfBST(int [] sequence) {        if(sequence.length == 0) return false;        int len = sequence.length;        return postTran(sequence, len - 1, 0, len - 2 );    }        public boolean postTran(int[] sequence, int len, int low, int high){        if(len <= 0 || low >= high) return true;        int index = low;        while(index < len){            if(sequence[index] > sequence[len]) break;            index++;        }        int flag = index;        while(index < len){            if(sequence[index] < sequence[len]) return false;            index++;        }        return postTran(sequence, flag - 1, low, flag - 2)             && postTran(sequence, high-1, flag, high-2);    }}