[PHP]算法- 判断是否为二叉搜索树的后序遍历序列的PHP实现
2023-02-18 15:41:48 时间
二叉搜索树的后序遍历序列: 输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出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);
相关文章
- 无需新型token mixer就能SOTA:MetaFormer视觉基线模型开源,刷新ImageNet记录
- 推荐一款神仙颜值的Redis客户端工具
- 首个在ImageNet上精度超过80%的二值神经网络BNext问世,-1与+1的五年辛路历程
- Redis+Guava,性能炸裂!这组合真的太顶了....
- 【eureka问题:已解决】Request execution failed with message: java.net.ConnectException: Connection refused:
- 【已解决】Cannot connect to the Docker daemon at unix:///var/run/docker.sock. Is the docker daemon runnin
- 【已解决】springboot在使用redisTemplate的测试的时候报空指针
- 差两个像素让我很难受,这问题绝不允许留到明年!
- React DevUI 18.0 正式发布🎉
- 好慌,我代码没了!不会是变基变出问题了吧?
- 老板:你为什么要选择 Vue?
- 实用的 Bash 快捷键
- Quill基本使用和配置 - DevUI
- Quill富文本编辑器的实践 - DevUI
- 如何解决异步接口请求快慢不均导致的数据错误问题? - DevUI
- 让我们一起建设 Vue DevUI 项目吧!🥳
- 号外号外!DevUI Admin V1.0 发布啦!
- 手把手教你搭建自己的Angular组件库 - DevUI
- 2021 年最值得推荐的 7 个 Angular 前端组件库 - DevUI
- 立完flag,你可能需要对flag进行量化