《剑指offer第二版》面试题33：二叉搜索树的后序遍历序列（j

题目描述

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

解题思路:

1. 二叉搜索树的左子树所有节点的值均小于根节点的值，右子树所有节点的值均大于根节点的值。
2. 后序遍历的最后一个数字为二叉树的根节点。
3. 由于没有重复数字，因此可遍历序列，找到第一个大于根据点的位置index，则index之前为左子树，index之后为右子树。
4. 检查右子树的序列值是否都大于根节点的值。
   1. 如果都大于，则index为界限，将序列分为前后两个序列，分别对着两个序列递归检查。
   2. 如果存在小于根节点的值，则不符合搜索二叉树的定义，直接返回false。

代码

boolean verifySequenceOfBST(int[] seqs){
    return verifySequenceOfBST(seqs, 0, seqs.length - 1);
}
boolean verifySequenceOfBST(int[] seqs, int start, int end){
    if (seqs == null ) {
        return false;
    }

    if ((end - start) <= 0) {
        return true;
    }

    int rootValue = seqs[end];

    // 找到左右子树的分解点
    int i = start;
    while (seqs[i] < rootValue) {
        i++;
    }

    // 验证右子树的序列值是否比root小
    for (int j = i + 1; j <= end; j++ ) {
        if (seqs[j] < rootValue) {
            // 说明非二叉搜索树
            return false;
        }
    }

    return verifySequenceOfBST(seqs, start, i - 1) && verifySequenceOfBST(seqs, i, end - 1);
}