題目

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

程序核心思想

后序遍歷是先遍歷左子樹，再遍歷右子樹，最后遍歷根節(jié)點(diǎn)。二叉搜索樹是對(duì)于每一個(gè)根節(jié)點(diǎn)來說，其左子樹的值小于根節(jié)點(diǎn)的值，右子樹的值大于根節(jié)點(diǎn)的值。
所以在這個(gè)題目中，如果是后序遍歷序列的話，最后一個(gè)值是根節(jié)點(diǎn)。可以先找到其左子樹的部分（小于根節(jié)點(diǎn)），然后看剩下的部分是不是右子樹（節(jié)點(diǎn)都小于根節(jié)點(diǎn)），如果是的話，則按上述辦法遞歸的檢查左子樹和右子樹的序列是否是后序遍歷序列。

Tips

無

代碼

public class Solution {
    public boolean VerifySquenceOfBST(int [] sequence) {
        if(sequence.length == 0)    return false;
        return youstart(sequence, 0, sequence.length-1);
        
    }
    
    public boolean youstart(int[] sequence, int start, int end){
        int i = start;
        for(; i < end; i++){
            if(sequence[i] > sequence[end]){
                return you(sequence, i, end-1, end) && youstart(sequence, start, i - 1) && youstart(sequence, i, end-1);
            }
        }
        return true;
        
    }
    
    public boolean you(int[] sequence, int start, int end, int key){
        for(int i = start; i <= end; i++){
            if(sequence[i] <= sequence[key]){
                return false;
            }
        }
        return true;
    }
}