[剑指offer][Java]二叉搜索树的后序遍历序列

题目

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

程序核心思想

后序遍历是先遍历左子树，再遍历右子树，最后遍历根节点。二叉搜索树是对于每一个根节点来说，其左子树的值小于根节点的值，右子树的值大于根节点的值。
所以在这个题目中，如果是后序遍历序列的话，最后一个值是根节点。可以先找到其左子树的部分（小于根节点），然后看剩下的部分是不是右子树（节点都小于根节点），如果是的话，则按上述办法递归的检查左子树和右子树的序列是否是后序遍历序列。

Tips

无

代码

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