题目33：二叉搜索树的后序遍历序列

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

举例说明

输入数组{5,7,6,9,11,10,8}，则返回true，因为这个整数序列是可以展开为一二叉搜索树的后序遍历结果。
如果输入的数组是{7,4,6,5}，则由于没有哪棵二叉搜索树的后序遍历结果是这个序列，因此返回false。

思路

和二叉树有关的问题，很多都可以递归解决，因为子问题和本问题具有一致性。关键是问题的划分和base case。

问题分解

先判断根结点的整颗树是否满足二叉搜索树左小右大的规律，再判断各个子树是否同样满足这种规律。

判断准则

在后序遍历得到的序列中， 最后一个数字是树的根结点的值。
数组中前面的数字可以分为两部分：

1. 第一部分是左子树结点的值，它们都比根结点的值小
2. 第二部分是右子树结点的值，它们都比根结点的值大。

代码实现

public class _33 {
    public static boolean verifySequenceOfBST(int[] sequence) {
        if (sequence == null || sequence.length < 1) {
            return false;
        }
        return verifySequenceOfBST(sequence, 0, sequence.length - 1);
    }

    private static boolean verifySequenceOfBST(int[] sequence, int start, int end) {
        // 如果对应要处理的数据只有一个或者已经没有数据要处理（start>end）就返回true
        if (start >= end) {// base case
            return true;
        }
        int index = start;
        while (index < end - 1 && sequence[index] < sequence[end]) {// 找右子树开始位置
            index++;
        }
        int right = index;// 记录下来。right为右子树开始的节点

        // 从右子树起点接着走，右子树的值都应该大于根节点
        while (index < end - 1 && sequence[index] > sequence[end]) {
            index++;// 应该要走到根节点前面 end-1
        }
        if (index != end - 1) {
            return false;// 说明根结点的右子树中有小于等于根结点的元素
        }
        return verifySequenceOfBST(sequence, start, right - 1) && verifySequenceOfBST(sequence, index, right - 1);
    }

    public static void main(String[] args) {
        //      8
        //    /  \
        //    6   10
        //   /\   /\
        //   5 7 9 11
        int[] sequence1 = { 5, 7, 6, 9, 11, 10, 8 };
        int[] sequence2 = { 7, 4, 6, 5 };
        System.out.println(verifySequenceOfBST(sequence1));// ture
        System.out.println(verifySequenceOfBST(sequence2));// false
    }
}

输出：

true
false