輸入一個(gè)整數(shù)數(shù)組搞挣，判斷該數(shù)組是不是某二叉搜索樹(shù)的后序遍歷的結(jié)果。假設(shè)輸入的數(shù)組的任意兩個(gè)數(shù)字都互不相同券盅。
思路一：
使用遞歸频敛，遞歸參數(shù)為序列以及開(kāi)始結(jié)束節(jié)點(diǎn)项郊，后序序列必然滿足最后一個(gè)節(jié)點(diǎn)作為根節(jié)點(diǎn)，前面分為兩部分姻政，一部分連續(xù)比根節(jié)點(diǎn)大呆抑，一部分連續(xù)比根節(jié)點(diǎn)小。每次循環(huán)找出分界點(diǎn)汁展，根據(jù)分界點(diǎn)遞歸鹊碍，出現(xiàn)一部分不滿足便是不滿足。
代碼如下:
/**
* 思路：
* 已知條件：后序序列最后一個(gè)值為root食绿；二叉搜索樹(shù)左子樹(shù)值都比root小侈咕，右子樹(shù)值都比root大。
* 1器紧、確定root耀销；
* 2、遍歷序列（除去root結(jié)點(diǎn)）铲汪，找到第一個(gè)大于root的位置熊尉，則該位置左邊為左子樹(shù)，右邊為右子樹(shù)掌腰；
* 3狰住、遍歷右子樹(shù)，若發(fā)現(xiàn)有小于root的值，則直接返回false；
* 4窖贤、分別判斷左子樹(shù)和右子樹(shù)是否仍是二叉搜索樹(shù)（即遞歸步驟1、2创南、3）。
* @param sequence
* @return
*/
public boolean VerifySquenceOfBST(int [] sequence) {
if (sequence == null || sequence.length <= 0){
return false;
}
return isSearchBST(sequence,0,sequence.length-1);
}
private boolean isSearchBST(int[] sequence, int begin, int end) {
//如果索引相等省核，必然為葉節(jié)點(diǎn)稿辙，如果小于必然不存在左子樹(shù)或者右子樹(shù)
if (begin >= end) return true;
int rootVal = sequence[end];
int i = begin;
//保證循環(huán)不越界
while (sequence[i] < rootVal && i < end){
i++;
}
//找到第一個(gè)大于根節(jié)點(diǎn)的作為分界點(diǎn)
int bound = i;
while (i < end){
//不越界情況下，出現(xiàn)小于則肯定不是
if (sequence[i] < rootVal) return false;
i++;
}
//子樹(shù)遞歸
return isSearchBST(sequence,begin,bound-1) && isSearchBST(sequence,bound,end-1);
}
思路二：非遞歸循環(huán)解決气忠，從后往前的所有數(shù)字邻储，對(duì)于它前面的數(shù)字要么連續(xù)比它小未桥，要么連續(xù)比它大，按照先比小芥备，后比大的兩個(gè)循環(huán)，如果最終順利到達(dá)當(dāng)前數(shù)字舌菜，即滿足萌壳，否則肯定不滿足。
/**
* 非遞歸
* 非遞歸也是一個(gè)基于遞歸的思想：
* 左子樹(shù)一定比右子樹(shù)小日月，因此去掉根后袱瓮，數(shù)字分為left，right兩部分爱咬，right部分的
* 最后一個(gè)數(shù)字是右子樹(shù)的根他也比左子樹(shù)所有值大尺借，因此我們可以每次只看有子樹(shù)是否符合條件
* 即可，即使到達(dá)了左子樹(shù)左子樹(shù)也可以看出由左右子樹(shù)組成的樹(shù)還像右子樹(shù)那樣處理
*
* 對(duì)于左子樹(shù)回到了原問(wèn)題精拟，對(duì)于右子樹(shù)燎斩，左子樹(shù)的所有值都比右子樹(shù)的根小可以暫時(shí)把他看出右子樹(shù)的左子樹(shù)
* 只需看看右子樹(shù)的右子樹(shù)是否符合要求即可
*/
public boolean VerifySquenceOfBST1(int [] sequence) {
int size = sequence.length;
if (sequence == null || size <= 0){
return false;
}
int i = 0;
while (--size >= 0){
while (sequence[i] < sequence[size]) i++;
while (sequence[i] > sequence[size]) i++;
//如果前面出現(xiàn)大小順序顛倒，不滿足先小后大的條件蜂绎，循環(huán)提前終止
if (i < size) return false;
i = 0;
}
return true;
}
