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

以最后一个为根，前找比根大的为右子树，剩下部分为左子树，检查左子树是否比根小

public class Solution {
    
    public boolean check(int[] sequence, int l, int r){
        if(l>=r)return true;
        int root, i, j;
        
        j = r;
        root = sequence[r];
        
        while(j>0&&sequence[j-1]>root)j--;
        for(i=l;i<j;i++){
            if(sequence[i]>root)return false;
        }
        
        return check(sequence,l,j-1)&&check(sequence,j,r-1);
    }
    
    
    public boolean VerifySquenceOfBST(int [] sequence) {
        if(sequence.length == 0)return false;
        return check(sequence, 0, sequence.length-1);
    }
}