So implementieren Sie PHP, um festzustellen, ob es sich um eine Post-Order-Traversal-Sequenz eines binären Suchbaums handelt (Code)

Der Inhalt dieses Artikels befasst sich damit, wie PHP die Post-Order-Traversal-Sequenz (Code) implementiert, um festzustellen, ob es sich um einen binären Suchbaum handelt Als Referenz können Freunde in Not darauf zurückgreifen. Ich hoffe, es wird Ihnen hilfreich sein.

Post-Order-Traversal-Sequenz des binären Suchbaums:
Geben Sie ein ganzzahliges Array ein, um zu bestimmen, ob das Array das Ergebnis der Post-Order-Traversal-Sequenz eines bestimmten binären Suchbaums ist. Wenn ja, geben Sie Ja aus, andernfalls geben Sie Nein aus. Nehmen Sie an, dass sich zwei beliebige Zahlen im Eingabearray voneinander unterscheiden.
Idee:

1. Die Durchquerung nach der Reihenfolge erfolgt nach links und rechts, das letzte Element ist der Wurzelknoten
2. Binärer Suchbaum, linker Teilbaum<=Wurzelknoten<=rechter Teilbaum
3. Durchqueren Sie das Array und finden Sie die erste Position, die größer als die Wurzel ist. Der linke Teilbaum ist der rechte Teilbaum.
Wenn es eine Position gibt, die kleiner als die Wurzel ist , return false
5. Rekursive linke und rechte Teilbäume

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

Das obige ist der detaillierte Inhalt vonSo implementieren Sie PHP, um festzustellen, ob es sich um eine Post-Order-Traversal-Sequenz eines binären Suchbaums handelt (Code). Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!