【剑指Offer 24】二叉搜索树的后序遍历序列

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

代码如下：

package demo;

public class Test24 {
    /**
     * @param sequence
     *            某二叉搜索树的后序遍历的结果
     * @return true：该数组是某二叉搜索树的后序遍历的结果；false：不是
     */
    public static boolean verifySequenceOfBST(int[] sequence) {
        // 输入的数组不能为空，并且必须有数据
        if (sequence == null || sequence.length <= 0) {
            return false;
        }
        return verifySequenceOfBST(sequence, 0, sequence.length - 1);
    }

    private static boolean verifySequenceOfBST(int[] sequence, int start, int end) {
        // 如果要处理的数据只有1个，或者已经没有数据需要处理，则返回true
        if (start >= end) {
            return true;
        }
        // 从左到右找不大于根节点（sequence[end]）的元素位置
        int index = start;
        while (index < end - 1 && sequence[index] < sequence[end]) {
            index++; // 执行完后，index之前的元素都是小于根节点的
        }
        // 记录第1个大于根节点的元素的位置
        int middle = index;
        // 保证接下来的元素，都大于根节点的值
        while (index < end - 1 && sequence[index] > sequence[end]) {
            index++; // 如果接下来的元素都大于根节点的值，则index会等于end-1
        }
        // 如果index不等于end-1，说明接下来的元素不是全部大于根节点的值
        if (index != end - 1) {
            return false;
        }
        // [start, index-1]：左子树
        // [index, end-1]：右子树
        index = middle;
        return verifySequenceOfBST(sequence, start, index - 1) && verifySequenceOfBST(sequence, index, end - 1);
    }

    public static void main(String[] args) {
        int[] data1 = { 4, 8, 6, 12, 16, 14, 10 };
        System.out.println("true:" + verifySequenceOfBST(data1));

        int[] data2 = { 4, 6, 7, 5 };
        System.out.println("true:" + verifySequenceOfBST(data2));

        int[] data3 = { 1, 2, 3, 4, 5 };
        System.out.println("true:" + verifySequenceOfBST(data3));

        int[] data4 = { 5, 4, 3, 2, 1 };
        System.out.println("true:" + verifySequenceOfBST(data4));

        int[] data5 = { 5 };
        System.out.println("true:" + verifySequenceOfBST(data5));

        int[] data6 = { 7, 4, 6, 5 };
        System.out.println("false:" + verifySequenceOfBST(data6));

        int[] data7 = { 4, 6, 12, 8, 16, 14, 10 };
        System.out.println("false:" + verifySequenceOfBST(data7));
    }
}

data1 data2 data3 data4

来源：http://blog.csdn.net/derrantcm/article/details/46705725