题解 | #二叉搜索树的后序遍历序列#

public class Solution {
    public boolean VerifySquenceOfBST(int [] sequence) {
        if(sequence.length == 0){
            return false;
        }
        return check(sequence);
    }
    
    public boolean check(int[] sequence){
       if(sequence.length == 0){
           return true;
       }
       int root = sequence[sequence.length-1];
        
       int index = 0;
        //前半段小于root
        while(index < sequence.length-1){
            if(sequence[index] > root){
                break;
            }
            index++;
        }
        //后半段大于root
        int tmp = index;
        while(tmp < sequence.length-1){
            if(sequence[tmp] < root){
                return false;
            }
            tmp++;
        }
        
        return check(Arrays.copyOfRange(sequence,0,index)) &&
            check(Arrays.copyOfRange(sequence,index,sequence.length-1));
        
        
        
    }
}