23、二叉树的后序遍历

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

public class Solution {
    public boolean VerifySquenceOfBST(int [] sequence) {
        if(sequence.length==0){
            return false;
        }
        return VerifySquenceOfBST(sequence, 0, sequence.length-1);
    }
    
    public boolean VerifySquenceOfBST(int [] sequence, int start, int end) {
        if(start==end){
            return true;
        }
        //后序遍历，最后一个元素是根
        int root = sequence[end];
        //左子树都小于root
        int i=start;
        while(sequence[i]<root&&i<end){
            i++;
        }
        
        //没有右子树
        if(i==end){
            return VerifySquenceOfBST(sequence,start,i-1);
        }
        
       
        //右子树都大于root，如果不满足，则返回false
        for(int j=i; j<end; j++){
            if(sequence[j]<root){
                return false;
            }
        }
        
        //没有左子树
        if(i==start){
            return VerifySquenceOfBST(sequence,i,end-1);
        }
        
        //递归检查左、右子树
        return VerifySquenceOfBST(sequence,start,i-1) 
            && VerifySquenceOfBST(sequence,i,end);
    }
}