이진 검색 트리의 후순 순회 시퀀스인지 확인하기 위해 PHP를 구현하는 방법(코드)

이 기사의 내용은 PHP가 이진 검색 트리인지 확인하기 위해 후위 순회 시퀀스(코드)를 구현하는 방법에 대한 것입니다. 필요한 친구는 이를 참조할 수 있습니다. 도움이 됩니다.

이진 탐색 트리의 후위 순회 순서:
정수 배열을 입력하고 그 배열이 특정 이진 탐색 트리의 후위 순회 결과인지 확인합니다. 그렇다면 Yes를 출력하고, 그렇지 않으면 No를 출력합니다. 입력 배열의 두 숫자가 서로 다르다고 가정합니다.
생각하기:

1. 후위 순회는 왼쪽과 오른쪽에 있으며 마지막 요소는 루트 노드입니다.
2. 이진 검색 트리, 왼쪽 하위 트리 <= 루트 노드<= 오른쪽 하위 트리
3. , 루트보다 큰 첫 번째 위치를 찾습니다. 이 위치의 왼쪽 하위 트리가 오른쪽 하위 트리입니다. 4. 루트보다 작은 하위 트리가 있으면 false를 반환합니다. 왼쪽 및 오른쪽 하위 트리를 반복합니다.

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 중국어 웹사이트의 기타 관련 기사를 참조하세요!