思路：
Paste_Image.png
后序遍歷為[5,7,6,9,11,10,8]
特點(diǎn)煤裙，先找到根節(jié)點(diǎn)8安拟，為序列最后一個(gè)元素盏求，遍歷整個(gè)序列中抖锥，大于根節(jié)點(diǎn)的為右子樹，小于根節(jié)點(diǎn)的為左子樹碎罚，所以可以使用遞歸來對(duì)子樹進(jìn)行同樣的操作磅废。如果遍歷的過程中，先出現(xiàn)了大于根節(jié)點(diǎn)的節(jié)點(diǎn)荆烈，后面又出現(xiàn)了小于根節(jié)點(diǎn)的節(jié)點(diǎn)拯勉，則說明不是二叉搜索樹的后序遍歷序列。比如[7,4,6,5]這樣的序列憔购。
public class Solution {
public boolean VerifySquenceOfBST(int [] sequence) {
int start,end;
start=0;
end=sequence.length;
if(end==0)
return false;
return Verify(sequence,start,end-1);
}
public boolean Verify(int [] sequence,int start,int end){
int i,j;
if(start<end){
for(i=start;i<end;i++){
if(sequence[i]>sequence[end])
break;
}
for(j=i;j<end;j++){
if(sequence[j]<sequence[end])
break;
}
if(j==end)
return Verify(sequence,start,i-1)&&Verify(sequence,i,end-1);
else
return false;
}else{
return true;
}
}
}
