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

牛客

描述

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则返回 true ,否则返回 false 。假设输入的数组的任意两个数字都互不相同。

最后一个数字是根节点，它的前面是左右两个子树。左子树都比根节点小，右子树都比根节点到，如果不能找到一个位置满足这个条件，说明这个数组不是二叉搜索树都后序遍历。然后依次对左右两子树进行重复操作。如果左子树或右子树不存在，返回 true 。

public boolean VerifySquenceOfBST(int [] sequence) {
    if(sequence==null || sequence.length==0) return false;
    return verifySquenceOfBST(sequence, 0, sequence.length-1);

}

private boolean verifySquenceOfBST(int[] sequence, int begin, int end){
    int root = sequence[end];
    int index=begin;
    for(;index<end;++index){
        if(sequence[index]>root) break;
    }
    for (int i = index; i < end; i++) {
        if(sequence[i]<root) return false;
    }
    boolean left=true, right=true;
    if (index != begin) {
        left = verifySquenceOfBST(sequence, begin, index-1);
    }
    if (index != end){
        right = verifySquenceOfBST(sequence, index, end-1);
    }
    return left && right;
}