欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

[PHP]算法- 判断是否为二叉搜索树的后序遍历序列的PHP实现

程序员文章站 2022-04-11 14:59:09
二叉搜索树的后序遍历序列: 输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。 思路: 1.后序遍历是 左右中 , 最后一个元素是根结点 2.二叉搜索树,左子树=end return true root=seq[... ......
二叉搜索树的后序遍历序列:
输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出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);