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

import java.util.*;
public class Solution {
     public boolean judgeBST(int [] sequence,int l,int r){
         if(l==r)
             return true;
         int i;
         for(i=l;i<r;i++){
             if(sequence[i]>=sequence[r])
                 break;
         }
         int mid=i;
         for(;i<r;i++){
             if(sequence[i]<sequence[r])
                 return false;
         }
         if(mid==l){
             //全是右子树
             return judgeBST(sequence,mid,r-1);
         }
         else if(mid==r){
             //全是左子树
             return judgeBST(sequence,l,mid-1);
         }else
         return judgeBST(sequence,l,mid-1)&&judgeBST(sequence,mid,r-1);
     }
    public boolean VerifySquenceOfBST(int [] sequence) {
        if(sequence.length==0)
            return false;
        if(sequence.length==1)
            return true;
        return judgeBST(sequence,0,sequence.length-1);
    }
}