JZ23：二叉搜索树的后序遍历序列

code1

• 结果的最后一位是根结点，找出左子树、右子树，

1. 首先判断右子树的结点值是不是都比根结点值大，

2. 然后判断左右子树是不是BST；

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

   code2

• 一次遍历确定出左右子树的分界点，然后再分别对两棵子树进行递归判断。

  public class Solution {
    public boolean VerifySquenceOfBST(int [] sequence) {
        if(sequence.length==0){
            return false;
        }
        return isBST(sequence,0,sequence.length-1);
    }
  
    public boolean isBST(int[] seq,int start,int end){
        if(start>=end){ // 可能出现start>end的情况
            return true;
        }
        int pivot;
        for(pivot=start;seq[pivot]<seq[end];pivot++);// 查找分界点
  
        for(int i=pivot;i<=end;i++){
            if(seq[i]<seq[end]){
                return false;
            }
        }
        return isBST(seq,start,pivot-1) && isBST(seq,pivot,end-1);
    }
  }