剑指Offer第二十三题：二叉搜索树的后序遍历序列

题目描述
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
解答：
思路：递归方法：一个n个数的数组，最后一位必定是根节点，前面n-1个数的前一半在左子树，后一半在右子树，那么就符合条件。对前后数据再做同样的判断。
public class Q_23 {

public boolean VerifySquenceOfBST(int[] sequence) {
    int len = sequence.length;
    if (len == 0) {
        return false;
    }
    int last = sequence[len - 1];
    boolean changed = false;
    boolean result = true;
    int changedPoint = 0;
    for (int i = 0; i < len - 1; i++) {
        if (!changed) {
            if (sequence[i] > last) {
                changed = true;
                changedPoint = i;
            }
        } else {
            if (sequence[i] < last) {
                result = false;
            }
        }

    }
    return result && (changedPoint < 2 || VerifySquenceOfBST(Arrays.copyOfRange(sequence, 0, changedPoint)))//或连接符前若满足，程序不走后面的递归
            && (len - changedPoint < 2 || VerifySquenceOfBST(Arrays.copyOfRange(sequence, changedPoint, len - 1)));

}

public static void main(String[] args) {
    int[] test = {4};
    System.out.println(new Q_23().VerifySquenceOfBST(test));
}

}