題目描述：

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

示例：

輸入：

[4,8,6,12,16,14,10]

返回：

TRUE

思路：

1. 首先，對于后序遍歷，數(shù)組的最后一位一定是該二叉樹的根節(jié)點；
2. 除去最后一位，數(shù)組中剩下的數(shù)字可以分為兩部分：
   -- 左子樹中的所有數(shù)字都比根節(jié)點小
   -- 右子樹中的所有數(shù)字都比根節(jié)點大
3. 遞歸判斷

code：

public class solution{
    public boolean VerifySquenceOfBST(int [] sequence) {
        if(sequence==null||sequence.length==0){
            return false;
        }
        return isBigger(sequence,0,sequence.length-1);
    }

    public boolean isBigger(int[] s, int start, int end){
        // 遞歸終止條件：
        // 已經(jīng)遍歷到最后，此時start = end
        if(start >= end){return true;}
        // 尋找第一個比s[end]大的數(shù)
        int index = 0;
        while(index != end){
        if(s[index] >  s[end]){break;}
        else{index++};
        }

        //在0-index之間的所有數(shù)都比s[end]小
        for(int i=start;i<index;i++){if(s[i]>s[end])return false;}
        //在index-end-1之間所有數(shù)都比s[end]大
        for(int i=index;i<end;i++){if(s[i]<s[end])return false;}

        return isBigger(s,start,index-1) && isBigger(s,index,end-1);
    }
}

特別注意：遞歸終止的條件是 start >=end而不是 start == end?。。?/strong>
如：

[4,5]