題目描述
輸入一個(gè)整數(shù)數(shù)組蟹肘，判斷該數(shù)組是不是某二叉搜索樹的后序遍歷的結(jié)果词疼。如果是則輸出Yes,否則輸出No。假設(shè)輸入的數(shù)組的任意兩個(gè)數(shù)字都互不相同帘腹。
public class Solution {
public boolean VerifySquenceOfBST(int [] sequence) {
if(sequence.length==0){
return false;
}
return VerifySquenceOfBST(sequence, 0, sequence.length-1);
}
public boolean VerifySquenceOfBST(int [] sequence, int start, int end) {
if(start==end){
return true;
}
//后序遍歷贰盗，最后一個(gè)元素是根
int root = sequence[end];
//左子樹都小于root
int i=start;
while(sequence[i]<root&&i<end){
i++;
}
//沒有右子樹
if(i==end){
return VerifySquenceOfBST(sequence,start,i-1);
}
//右子樹都大于root，如果不滿足阳欲，則返回false
for(int j=i; j<end; j++){
if(sequence[j]<root){
return false;
}
}
//沒有左子樹
if(i==start){
return VerifySquenceOfBST(sequence,i,end-1);
}
//遞歸檢查左舵盈、右子樹
return VerifySquenceOfBST(sequence,start,i-1)
&& VerifySquenceOfBST(sequence,i,end);
}
}
