当前位置:Gxlcms > PHP教程 > php如何实现判断是否为二叉搜索树的后序遍历序列(代码)

php如何实现判断是否为二叉搜索树的后序遍历序列(代码)

时间:2021-07-01 10:21:17 帮助过:8人阅读

本篇文章给大家带来的内容是关于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如何实现判断是否为二叉搜索树的后序遍历序列(代码)的详细内容,更多请关注Gxl网其它相关文章!

人气教程排行