【题33 二叉搜索树的后序遍历】

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

【思路】

【实现】

public class Solution {
    public boolean VerifySquenceOfBST(int [] sequence) {
        if(sequence.length==0)return false;
        return IsTree(sequence,0,sequence.length-1);
    }
    public boolean IsTree(int[] sequence,int start,int end){
        if(end<= start)return true;
        int i = start;
        for(;i<end;i++){//找到左子树
            if(sequence[i]>sequence[end])break;
        }
        for(int j = i;j<end;j++){//找到右子树
            if(sequence[j]<sequence[end])return false;
        }
        return IsTree(sequence,start,i-1) &&IsTree(sequence,i,end-1);
    }
}

参考1.《剑指offer》
2.https://www.nowcoder.com/profile/919147/codeBookDetail?submissionId=1522814