輸入一個(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;
    }
}