題目33：二叉搜索樹的后序遍歷序列

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

舉例說明

輸入數(shù)組{5,7,6,9,11,10,8}，則返回true，因為這個整數(shù)序列是可以展開為一二叉搜索樹的后序遍歷結(jié)果。
如果輸入的數(shù)組是{7,4,6,5}，則由于沒有哪棵二叉搜索樹的后序遍歷結(jié)果是這個序列，因此返回false。

思路

和二叉樹有關(guān)的問題，很多都可以遞歸解決，因為子問題和本問題具有一致性。關(guān)鍵是問題的劃分和base case。

問題分解

先判斷根結(jié)點的整顆樹是否滿足二叉搜索樹左小右大的規(guī)律，再判斷各個子樹是否同樣滿足這種規(guī)律。

判斷準則

在后序遍歷得到的序列中， 最后一個數(shù)字是樹的根結(jié)點的值。
數(shù)組中前面的數(shù)字可以分為兩部分：

1. 第一部分是左子樹結(jié)點的值，它們都比根結(jié)點的值小
2. 第二部分是右子樹結(jié)點的值，它們都比根結(jié)點的值大。

代碼實現(xiàn)

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) {
        // 如果對應要處理的數(shù)據(jù)只有一個或者已經(jīng)沒有數(shù)據(jù)要處理（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為右子樹開始的節(jié)點

        // 從右子樹起點接著走，右子樹的值都應該大于根節(jié)點
        while (index < end - 1 && sequence[index] > sequence[end]) {
            index++;// 應該要走到根節(jié)點前面 end-1
        }
        if (index != end - 1) {
            return false;// 說明根結(jié)點的右子樹中有小于等于根結(jié)點的元素
        }
        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