[PHP] 算法-根据前序和中序遍历结果重建二叉树的PHP实现
2023-02-18 15:47:20 时间
输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建二叉树并返回。 1.前序遍历是中,左,右;中序遍历是左,中,右 2.前序遍历的第一个是根结点,中序遍历数组中从开始到根结点的所有是左子树,可以知道左子树的个数,根结点右边的是右子树 3.前序遍历除去0位置的,从1到左子树个数位置是左子树,其他的是右子树 4.确定四个数组,前序左子树数组,前序右子树数组,中序左子树数组,中序右子树数组;递归调用 reConstructBinaryTree(pre,in) if(pre.length) return null//递归终止条件 root=pre[0] Node=new Node(root) //在中序中找根结点的位置 p=0 for p;p<pre.length;p++ if in[p]==root break for i=0;i<pre.length;i++ if i<p //中序左子树数组 inLeft[]=in[i] //前序左子树数组 preLeft[]=pre[i+1] else if i>p //中序的右子树 inRight[]=in[i] //前序的右子树 preRight[]=pre[i] Node->left=reConstructBinaryTree(preLeft,inLeft) Node->right=reConstructBinaryTree(preRight,inRight) return Node
<?php class TreeNode{ var $val; var $left = NULL; var $right = NULL; function __construct($val){ $this->val = $val; } }; function reConstructBinaryTree($pre, $vin){ $len=count($pre); if($len==0){ return null; } $root=$pre[0]; $node=new TreeNode($root); for($p=0;$p<$len;$p++){ if($vin[$p]==$root){ break; } } $preLeft=array(); $preRight=array(); $vinLeft=array(); $vinRight=array(); for($i=0;$i<$len;$i++){ if($i<$p){ $preLeft[]=$pre[$i+1]; $vinLeft[]=$vin[$i]; }else if($i>$p){ $preRight[]=$pre[$i]; $vinRight[]=$vin[$i]; } } $node->left=reConstructBinaryTree($preLeft,$vinLeft); $node->right=reConstructBinaryTree($preRight,$vinRight); return $node; } $pre=array(1,2,4,7,3,5,6,8); $vin=array(4,7,2,1,5,3,8,6); $node=reConstructBinaryTree($pre,$vin);; var_dump($node);
object(TreeNode)#1 (3) { ["val"]=> int(1) ["left"]=> object(TreeNode)#2 (3) { ["val"]=> int(2) ["left"]=> object(TreeNode)#3 (3) { ["val"]=> int(4) ["left"]=> NULL ["right"]=> object(TreeNode)#4 (3) { ["val"]=> int(7) ["left"]=> NULL ["right"]=> NULL } } ["right"]=> NULL } ["right"]=> object(TreeNode)#5 (3) { ["val"]=> int(3) ["left"]=> object(TreeNode)#6 (3) { ["val"]=> int(5) ["left"]=> NULL ["right"]=> NULL } ["right"]=> object(TreeNode)#7 (3) { ["val"]=> int(6) ["left"]=> object(TreeNode)#8 (3) { ["val"]=> int(8) ["left"]=> NULL ["right"]=> NULL } ["right"]=> NULL } } }
相关文章
- Jmeter系列(40)- 详解 Jmeter 图形化 HTML 压测报告
- Jmeter系列(39)- 详解 Jmeter CLI 模式
- Jmeter系列(38)- Jmeter 分布式测试
- Jmeter系列(37)- 跨平台运行 Jmeter,CSV 文件路径设置
- Jenkins操作手册 - 巨详细,一篇足矣!
- 【JVM实战系列】「监控调优体系」实战开发arthas-spring-boot-starter监控你的微服务是否健康
- 【Spring专题】「开发指南」夯实实战基础功底之解读logback-spring.xml文件的详解实现
- 精华推荐 |【深入浅出Sentinel原理及实战】「原理探索专题」完整剖析Alibaba微服务架构体系之轻量级高可用流量控制组件Sentinel(1)
- 【深入浅出Spring原理及实战】「源码原理实战」从底层角度去分析研究PropertySourcesPlaceholderConfigurer的原理及实战注入机制
- 精华推荐 | 【深入浅出RocketMQ原理及实战】「性能原理挖掘系列」透彻剖析贯穿RocketMQ的事务性消息的底层原理并在分析其实际开发场景
- 深度剖析 | 【JVM深层系列】[HotSpotVM研究系列] JVM调优的"标准参数"的各种陷阱和坑点分析(攻克盲点及混淆点)「 1 」
- 【JVM故障问题排查心得】「内存诊断系列」Docker容器经常被kill掉,k8s中该节点的pod也被驱赶,怎么分析?
- 【深入浅出SpringCloud原理及实战】「SpringCloud-Alibaba系列」微服务模式搭建系统基础架构实战指南及版本规划踩坑分析
- 【秒杀购物商城业务服务】「分布式架构服务」盘点中间件服务的高可用模式及集群技术的方案分析
- 作者推荐 | 【分布式技术专题】「架构设计方案」图解学习法总结集群模式下的各种软负载均衡策略实现及原理分析
- 【分布式技术专题】「架构设计方案」盘点和总结秒杀服务的功能设计及注意事项技术体系
- Kafka技术专题之「性能调优篇」消息队列服务端出现内存溢出OOM以及相关性能调优实战分析
- 深入浅出学习透析Nginx服务器的基本原理和配置指南「初级实践篇 」
- 深入浅出学习透析 Nginx 服务器的基本原理和配置指南「运维操作实战篇」
- 【JVM故障问题排查心得】「内存诊断系列」JVM内存与Kubernetes中pod的内存、容器的内存不一致所引发的OOMKilled问题总结(下)