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

2021年9月14日21:06:06
还有种栈的 懒得看了

最后的r-1
return recur(sequence,l,i-1) && recur(sequence,i,r-1)
没有检查出来
1.分治递归

public class Solution {
    public boolean VerifySquenceOfBST(int [] sequence) {
        if(sequence.length == 0) return false;
        return recur(sequence,0,sequence.length-1);

    }
    public boolean recur(int [] sequence, int l, int r){
        //判断[l r]区间是不是一个二叉搜索树
        if(l>=r) return true;

        int root = sequence[r];
        int i = l;
//搜索到右子树的开始
        for(; i<r;i++){
            if(sequence[i] > root) break;
        }
        //左子树判断是不是符合条件
        for(int j = l; j<i ;j++){
            if(sequence[j] > root) return false;
        }
        //右子树判断是不是符合条件
        for(int j = i; j<r ;j++){
            if(sequence[j] < root) return false;
        }
        //返回左右子树数
        return recur(sequence,l,i-1) && recur(sequence,i,r-1);

    }
}