二叉搜索树的后续遍历序列

题目：

​ 输入一个整数数组，判断该数组是不是某个二叉搜索树的后续遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。例如，输入数组 {5, 7, 6, 9, 11, 10, 8}，则返回 true，因为这个整数序列是下图中二叉搜索树的后续遍历结果。如果输入的数组是 {7, 4, 6, 5}，则由于没有哪棵二叉树的后续遍历结果是这个序列，因此返回 false。

分析：

​ 在后序遍历序列中，最后一个数字是树的根节点。数组中前面的数字可以分为两部分：第一部分是左子树节点的值，它们都比根节点的值小；第二部分是右子树节点的值，它们都比根节点的值大。

​ 以数组 {5, 7, 6, 9, 11, 10, 8} 为例，后序遍历结果的最后一个数字 8 就是根节点的值。在这个数组中，前 3 个数字 5、7、6 都比 8 小，是 8 的左子树节点；后 3 个数字9、11、10 都比 8 大，是 8 的右子树节点。

​ 接下来以同样的方法来确定与数组每一部分对应的子树的结构。这其实是一个递归的过程。对于序列 {5, 7, 6} 来讲，最后一个数字 6 是左子树根节点的值。数字 5 比 6 小，是 6 的左子节点，而 7 则是 6 的右子节点。同理，在序列 {9, 11, 10} 中，10 是右子树的根节点， 9 是 10 的左子节点， 11 是 10 的右子节点。

代码：

public class CheckSearchTreeSequence {

    /**
     * 是否二叉搜索树的后序遍历序列
     *
     * @param sequence 数组序列
     * @param length   数组长度
     * @return
     */
    public static boolean isPostOrder(int[] sequence, int length) {

        if (null == sequence || length <= 0) {
            return false;
        }

        // 左右子树分界index
        int separateIndex = 0;
        // 根节点的值
        int root = sequence[length - 1];

        // 二叉搜索树中左子树节点的值小于根节点的值
        for (int i = 0; i < length; i++) {
            if (sequence[i] > root) {
                separateIndex = i;
                break;
            }
        }

        // 二叉搜索树中右子树节点的值大于根节点的值
        for (int i = separateIndex; i < length; i++) {
            if (sequence[i] < root) {
                return false;
            }
        }

        // 判断左子树是否二叉搜索树
        boolean left = true;
        // 判断右子树是否二叉搜索树
        boolean right = true;

        if (separateIndex > 0) {
            left = isPostOrder(sequence, separateIndex);
        }

        // 判断右子树时从序列中排除根节点
        if (separateIndex < length - 1) {
            right = isPostOrder(sequence, length - separateIndex - 1);
        }

        return left && right;
    }
}

测试：

public class TestCheckSearchTreeSequence {

    @Test
    public void test() {
        int[] sequence = {5, 7, 6, 9, 11, 10, 8};
        int length = 7;

        System.out.println(CheckSearchTreeSequence.isPostOrder(sequence, length));
    }
}