[PHP]演算法- 判斷是否為二叉搜索樹的後序遍歷序列的PHP實現

二叉搜索樹的後序遍歷序列：
輸入一個整數數組，判斷該數組是不是某二叉搜索樹的後序遍歷的結果。如果是則輸出Yes,否則輸出No。假設輸入的數組的任意兩個數字都互不相同。

思路：
1.後序遍歷是 左右中 ， 最後一個元素是根結點 
2.二叉搜索樹，左子樹<=根結點<=右子樹
3.遍曆數組，找到第一個大於root的位置，該位置左面為左子樹，右面為右子樹
4.遍歷右子樹，如果有小於root的返回false
5.遞歸左右左右子樹

VerifySquenceOfBST(seq)
    judge(seq,0,seq.size-1)
judge(seq,start,end)
    if start>=end return true
    root=seq[end]
    index
    for i=start;i<end;i++
        if seq[i]>= root
            index=i
            break
    for i=index;i<end;i++
        if seq[i]<root
            return false
    return judge(seq,start,index-1) && judge(seq,index,end-1)

<?php

function judge($seq,$start,$end){
        if(empty($seq)) return false;
        //跳出條件
        if($start>=$end) return true;
        $root=$seq[$end];
        $index=$end;
        //找出第一個大於root的位置
        for($i=$start;$i<$end;$i++){
                if($seq[$i]>=$root){
                        $index=$i;
                        break;
                }   
        }   
        //查找右子樹中如果有小於root的返回false
        for($i=$index;$i<$end;$i++){
                if($seq[$i]<$root){
                        return false;
                }   
        }   
        //短路語法遞歸調用
        return judge($seq,$start,$index-1) && judge($seq,$index,$end-1);
}

function VerifySquenceOfBST($sequence)
{
    return judge($sequence,0,count($sequence)-1);
}

$seq=array(1,2,3);
$bool=VerifySquenceOfBST($seq);
var_dump($bool);