輸入一個(gè)整數(shù)數(shù)組蚀狰，判斷該數(shù)組是不是某二叉搜索樹的后序遍歷的結(jié)果。如果是則輸出Yes,否則輸出No职员。假設(shè)輸入的數(shù)組的任意兩個(gè)數(shù)字都互不相同麻蹋。
一個(gè)二叉樹結(jié)構(gòu)是不能僅僅根據(jù)后續(xù)遍歷確定的，但是題目中的二叉樹是二叉搜索樹焊切，二叉搜索樹的性質(zhì)是節(jié)點(diǎn)左子樹的值一定小于根節(jié)點(diǎn)扮授，右子樹的值一定都大于根節(jié)點(diǎn)，后續(xù)遍歷的順序是先左然后右最后根節(jié)點(diǎn)专肪，所以序列的最后一個(gè)元素一定是根節(jié)點(diǎn)刹勃。曾想過既然最后一個(gè)元素是根節(jié)點(diǎn)，自己能不能根據(jù)二叉搜索樹的性質(zhì)和給定的序列能否構(gòu)建出一個(gè)搜索樹呢嚎尤。比如給定測試序列[4,8,6,12,16,14,10]荔仁，其中10是根節(jié)點(diǎn)，14大于10所以14應(yīng)該在10的右子樹芽死，16大于14乏梁，16位于14的右子樹，12大于10小于14所以位于14的左子樹...... 就這樣構(gòu)建关贵，完成后然后在進(jìn)行一次后序遍歷然后和給定的序列進(jìn)行比較是否一致遇骑。但是這樣實(shí)在太麻煩了。而且題目中沒有給定樹的結(jié)構(gòu)揖曾，說明題目不需要進(jìn)行先構(gòu)建二叉搜索樹然后進(jìn)行后序遍歷再比較序列的一致性來求解落萎。所以還是考慮二叉搜索樹的性質(zhì)和樹的遞歸結(jié)構(gòu)，二叉搜索樹的節(jié)點(diǎn)除了大小性質(zhì)外炭剪，每個(gè)子樹同樣是二叉搜索樹练链。所以完全可以遞歸求解。求解思路：如果給定的序列符合奴拦，根據(jù)后續(xù)的遍歷一定可以找到根節(jié)點(diǎn)的左子樹的遍歷序列和右子書的遍歷序列兑宇。左邊的都一定比根節(jié)點(diǎn)小，右邊的都比根節(jié)點(diǎn)大，有一個(gè)不符合就返回false隶糕。如果符合就遞歸的求解左序列和右序列瓷产。如果每次遞歸都符合說明給定序列符合條件。其中遇到的一個(gè)問題是如果序列為空應(yīng)該怎么判斷枚驻，因?yàn)橐粋€(gè)二叉搜索樹僅僅有左子樹或者右子樹是可能的濒旦，所以我之前判斷如果序列元素的數(shù)量小于等于1應(yīng)該返回true。但是如果第一次輸入給函數(shù)的時(shí)候就是空序列再登，顯然是不應(yīng)該返回true的尔邓。所以如果序列為空返回false，后面進(jìn)行遞歸之前如果子序列為空就不遞歸來實(shí)現(xiàn)锉矢。
function VerifySquenceOfBST($sequence)
{
// write code here
$flag = true;
if(count($sequence)==0){
return false;
}
if(count($sequence)==1){
return true;
}
else{
$root_val = end($sequence);
$less_max_idx = -1 ;
$left = array();
$right = array();
for($i = 0;$i < count($sequence);$i++){
if($sequence[$i]<$root_val){
$less_max_idx = $i;
}
}
for($i = 0;$i<count($sequence)-1;$i++){
if($i<=$less_max_idx){
$left[] = $sequence[$i];
}else{
$right[] = $sequence[$i];
}
}
//驗(yàn)證左子樹,必須都比根節(jié)點(diǎn)小
for($i =0;$i<count($left);$i++){
if($left[$i] > $root_val){
return false;
}
}
for($i = 0; $i<count($right); $i++){
if($right[$i] < $root_val){
return false;
}
}
if(count($left)>0){
$flag &= VerifySquenceOfBST($left);
}
if($flag&&count($right)>0){
$flag &= VerifySquenceOfBST($right);
}
return $flag;
}
}
