題目描述
????輸入一個(gè)整數(shù)數(shù)組，判斷該數(shù)組是不是二叉搜索樹(shù)的后續(xù)遍歷結(jié)果，假設(shè)輸入數(shù)組的元素互不相等赂韵。
解題思路
????如下圖的后續(xù)遍歷序列為squence{5,7,6,9,11,10,8}送淆，對(duì)于序列數(shù)組squence，最后一個(gè)元素8即為樹(shù)的根節(jié)點(diǎn)致板，我們以根節(jié)點(diǎn)為標(biāo)準(zhǔn)交煞，從左往右搜索序列，左子樹(shù)中的節(jié)點(diǎn)均小于根節(jié)點(diǎn)得到左子樹(shù)序列{5,7,6}斟或，右子樹(shù)中的節(jié)點(diǎn)均大于根節(jié)點(diǎn)得到右子樹(shù)序列{9,11,10}素征，左右子樹(shù)以此遞歸搜索判斷。
二叉搜索樹(shù)
Java代碼實(shí)現(xiàn)
/**
* 給定一個(gè)數(shù)組形式的數(shù)列判斷是否二叉搜索樹(shù)的后續(xù)遍歷萝挤，遞歸解法
* @author Administrator
* @version 2018/10/12
*/
public class Exe34_VerifySquenceOfBST {
public static void main(String[] args) {
int[] squence={5,7,6,9,11,10,8};
System.out.println(verifySequenceOfBST(squence, 0, squence.length-1));
}
public static boolean verifySequenceOfBST(int[] squence,int startIndex,int endIndex) {
if(squence==null||startIndex<0||startIndex>squence.length-1
||endIndex<startIndex||endIndex>squence.length-1) return false;
else {
//首先根據(jù)根節(jié)點(diǎn)(序列最后一個(gè))將序列分成左右子樹(shù)序列并判斷合法性
int root=squence[endIndex];
int i=startIndex;
for(;i<endIndex;i++){
if(squence[i]>root)
break;
}
int j=i;
for(;j<endIndex;j++){
if(squence[j]<root)
return false;
}
//遞歸判斷子序列的合法性
boolean isLeftLeagel=true;
if(startIndex<i-1){//注意這里條件判斷御毅，如果子序列長(zhǎng)度為0，那么它也是合法的
isLeftLeagel=verifySequenceOfBST(squence, startIndex, i-1);
}
boolean isRightLeagel=true;
if(i<endIndex-1){//注意這里條件判斷怜珍，如果子序列長(zhǎng)度為0端蛆，那么它也是合法的
isRightLeagel=verifySequenceOfBST(squence, i, endIndex-1);
}
return isLeftLeagel&&isRightLeagel;
}
}
}
