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

二叉搜索树：右子树的所有结点大于根，左子树的所有结点小于根。

注意点：递归结束条件

public class Solution {
    public boolean VerifySquenceOfBST(int [] sequence) {
        if(sequence.length == 0) return false;
        if(sequence.length == 1) return true;
        return postOrderBST(sequence, 0, sequence.length-1);
    }
   
    public boolean postOrderBST(int[] s, int start, int root){
        if(start >= root) return true;//数组为0或1时无需判断
        int i = root;//找到比根小的元素位置
        while(i>start && s[i-1]>s[root]){
            i--;
        }
        for(int j=start; j<i-1; j++){//判断左子树是否符合要求
            if(s[j] > s[root]){
                return false;
            }
        }
        return postOrderBST(s, start, i-1) && postOrderBST(s, i, root-1);//递归
    }
}

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

原文：https://www.cnblogs.com/dyq19/p/10547534.html