How to implement PHP to determine whether it is a post-order traversal sequence of a binary search tree (code)

The content of this article is about how PHP implements the post-order traversal sequence (code) to determine whether it is a binary search tree. There are certain For reference value, friends in need can refer to it. I hope it will be helpful to you.

Post-order traversal sequence of binary search tree:
Input an integer array to determine whether the array is the result of post-order traversal of a certain binary search tree. If yes, output Yes, otherwise output No. Assume that any two numbers in the input array are different from each other.
Idea:

1. Post-order traversal is left and right, and the last element is the root node
2. Binary search tree, left subtree<=root node<=right Subtree
3. Traverse the array and find the first position that is greater than root. The left subtree of this position is the left subtree and the right subtree is the right subtree.
4. Traverse the right subtree. If there is one smaller than root, return false
5. Recursive left and right subtrees

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

The above is the detailed content of How to implement PHP to determine whether it is a post-order traversal sequence of a binary search tree (code). For more information, please follow other related articles on the PHP Chinese website!