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);

以上是php如何實現判斷是否為二元搜尋樹的後序遍歷序列（程式碼）的詳細內容。更多資訊請關注PHP中文網其他相關文章！