題目：輸入一個(gè)整數(shù)數(shù)組，判斷該數(shù)組是不是某二叉搜索樹的后序遍歷的結(jié)果。如果是則返回true。否則返回false。假設(shè)輸入的數(shù)組的任意兩個(gè)數(shù)字都互不相同。

代碼如下：

package demo;

public class Test24 {
    /**
     * @param sequence
     *            某二叉搜索樹的后序遍歷的結(jié)果
     * @return true：該數(shù)組是某二叉搜索樹的后序遍歷的結(jié)果；false：不是
     */
    public static boolean verifySequenceOfBST(int[] sequence) {
        // 輸入的數(shù)組不能為空，并且必須有數(shù)據(jù)
        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) {
        // 如果要處理的數(shù)據(jù)只有1個(gè)，或者已經(jīng)沒有數(shù)據(jù)需要處理，則返回true
        if (start >= end) {
            return true;
        }
        // 從左到右找不大于根節(jié)點(diǎn)（sequence[end]）的元素位置
        int index = start;
        while (index < end - 1 && sequence[index] < sequence[end]) {
            index++; // 執(zhí)行完后，index之前的元素都是小于根節(jié)點(diǎn)的
        }
        // 記錄第1個(gè)大于根節(jié)點(diǎn)的元素的位置
        int middle = index;
        // 保證接下來的元素，都大于根節(jié)點(diǎn)的值
        while (index < end - 1 && sequence[index] > sequence[end]) {
            index++; // 如果接下來的元素都大于根節(jié)點(diǎn)的值，則index會等于end-1
        }
        // 如果index不等于end-1，說明接下來的元素不是全部大于根節(jié)點(diǎn)的值
        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