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

输入一个整数数组，以确定该数组是否是遍历二叉搜索树的结果. 如果是，则输出“是”，否则输出“否”. 假设输入数组中的任何两个数字互不相同.

思考:

在通过后序遍历获得的序列中，最后一个元素是根节点. 数组中的前元素可以分为两部分序列二叉排序树，左部分小于根节点序列二叉排序树，即左子树，

右侧部分大于根节点，并且是右侧子树.

public class Solution {
    public boolean VerifySquenceOfBST(int [] sequence) {
        if(sequence.length==0) return false;
        if(sequence.length==1) return true;
        return ju(sequence, 0, sequence.length-1);
    }
    public boolean ju (int [] a,int start,int root){
        if(start>root) return true;
        int i = root;
        while(i>start &&a[i-1]>a[root]){
            i--;
        }
        for(int j= start;j < i-1;j++){
            if(a[j]>a[root])
                return false;
        }
        return ju(a,start,i-1)&& ju(a,i,root-1);
        }
}

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-242358-1.html