判斷二叉搜尋樹的後序周遊序列問題

public class Solution {
    public boolean VerifySquenceOfBST(int [] sequence) {
        if(sequence==null||sequence.length==0) return false;
        if(sequence.length==1) return true;
        return find(sequence,0,sequence.length-1);
    }
    public boolean find(int[] array,int start,int end){
        if(start>=end)return true;
        //int root=;
        int i=end;
        while(i>start&&array[i-1]>array[end])
        {
            i--;
        }
      
        for(int j=start;j<=i-1;j++){
            if(array[j]>array[end])
            return false;
        }
        return find(array,start,i-1)&&find(array,i,end-1);
    }
}
           

後序周遊的特點就是根節點在最後，結合二叉搜尋樹的性質，根節點的左子樹值均小于根節點，右子樹值均大于根節點。是以，我們可以得到，在給定數組中，凡是小于根節點的為左子樹部分，大于根節點的為右子樹部分。但是如果在左子樹中找到大于根節點，或在右子樹中找到小于根節點的，則給定序列就不是後序周遊的結果。

這裡我用遞歸的思想，将一個數組問題利用分治的思想，從後往前查找，直到第一次找到小于根節點的值array[i-1]，這個值作為左子樹的根節點，相對應的i~end-1的部分就是我們的右子樹了。一層一層遞歸下去就是我們想要的結果。