专栏首页陶士涵的菜地[PHP]算法- 判断是否为二叉搜索树的后序遍历序列的PHP实现

[PHP]算法- 判断是否为二叉搜索树的后序遍历序列的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);

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • [Linux] 使用tcpdump查看上传文件过程中的tcp传输过程

    客户端===>服务器[S] 标志位SYN 是1 , mss 65495 (每个包传输的最大数据部分是65495字节) seq序列号是87768135

    陶士涵
  • [PHP]垃圾回收机制

    2. 在zval结构体中定义了ref_count和is_ref , ref_count是引用计数 ,标识此zval被多少个变量引用 , 为0时会被销毁 is_r...

    陶士涵
  • [日常] go语言圣经-获取URL练习题

    2.http.Get函数是创建HTTP请求的函数,resp这个结构体中,Body字段包括一个可读的服务器响应流

    陶士涵
  • R语言之可视化①⑥一页多图(2)目录

    cowplot包是ggplot2的简单附加组件。 它旨在为ggplot2提供一个出版物就绪的主题,这个主题需要最少量的轴标签尺寸,情节背景等。对'ggplot2...

    用户1359560
  • LaTeX系列:基本框架

    详细代码百度云链接:http://pan.baidu.com/s/1hrNF1Rm

    努力在北京混出人样
  • 谷歌为搜索加密,挑战NSA和中国的网络审查

    “谷歌为搜索加密,挑战美国国家安全局(NSA)和中国的网络审查”,美国媒体报道称,这是美国前情报人员斯诺登爆料“NSA监控全球互联网”丑闻带来的 最新、也可能...

    安恒信息
  • Python数据可视化——matplotlib使用

    总第57篇 01|Figure和Subplot: matplotlib的图像都位于figure对象中,相当于一块画布。figure的属性figsize是用来设置...

    张俊红
  • 「R」cowplot(四)图形排列

    如果你指定labels="AUTO"或labels="auto",那么标签会自动按照大写或小写排列:

    王诗翔呀
  • 【R语言入门】R语言环境搭建

    R 语言是一个功能十分强大的工具,几乎绝大多数的数据分析工作都可以在 R 中完成,并且拥有很极强的绘图功能支持,能让你手中的数据以各种姿势进行可视化呈现,而且支...

    弗兰克的猫
  • python matplotlib.pyplot.plot()参数用法

    默认情况下,每个行被指定一个由“颜色周期”指定的不同颜色。要改变这种行为,可以编辑axes.color_cycle中的rcparam。

    砸漏

扫码关注云+社区

领取腾讯云代金券