剑指offer之判断一个数组是否为二叉搜索树的后序遍历

image.png

这道题目的核心思想还是在于对二叉搜索树的理解,以及使用递归来解决树的问题,刚开始看到题目的时候居然去谷歌了一下二叉搜索树,看来应该复习一下数据结构知识了,都说准备算法是一个比较玄学的东西,但是还是要积累经验吧,哪来的那么多的天才啊,经验就是智慧。

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

在最后一个for循环判断的取值上面花了很长时间,就是这条语句,
for(int i = start; i < j;i++)
如果写成i <= j,结果就不通过,测试样例不能通过,去掉之后就可以通过,最后还是在极限情况处出现了问题,当测试用例为5,4,3,2,1的时候,这是一颗只有右子树,没有左子树的二叉搜索树,这时候退出while循环是因为破坏了j > start的条件,这时候j = 0;但是如果加上“=”的话,for循环里面还是要进行
sequence[i] > sequence[end]的判断,这时候5 > 1,返回false,导致了最终的不通过。