每天一道算法_9_由后序遍历和中序遍历求前序遍历

假设一棵二叉树的后序遍历序列为 DGJHEBIFCA ,中序遍历序列为 DBGEHJACIF ,求前序遍历。 整体思路是这样的,由后序遍历找到每个节点,然后由中序遍历判断左右子树,将整个二叉树还原后写出前序遍历。后序遍历的顺序知道,最后一个A是二叉树的根节点,然后把中序遍历从A分成两段,A左边的是左子树,A右边的是右子树,结果如下 然后看右边的子树,从后序遍

大家好,又见面了,我是全栈君。

假设一棵二叉树的后序遍历序列为 DGJHEBIFCA ,中序遍历序列为 DBGEHJACIF ,求前序遍历。

 

整体思路是这样的,由后序遍历找到每个节点,然后由中序遍历判断左右子树,将整个二叉树还原后写出前序遍历。

后序遍历的顺序知道,最后一个A是二叉树的根节点,

然后把中序遍历从A分成两段,A左边的是左子树,A右边的是右子树,

结果如下

每天一道算法_9_由后序遍历和中序遍历求前序遍历

 

然后看右边的子树,

从后序遍历知道,左子树的后序遍历为IFC,中序遍历为CIF

问题回到刚开始,重复之前的过程,由后序遍历知道根节点为C,把中序遍历从C分成两段,

左边是左子树,右边是右子树

也就是右边只有一个右子树,

每天一道算法_9_由后序遍历和中序遍历求前序遍历

 

然后再次重复以上过程,现在IF的后序遍历是IF,中序遍历是IF,说明

节点时F,I是F的左子树

每天一道算法_9_由后序遍历和中序遍历求前序遍历

 

这样,这棵二叉树的右子树就完全复原了,左子树的方法完全相同,就是一个递归过程,流程图如下

 

每天一道算法_9_由后序遍历和中序遍历求前序遍历

 

 

NEXT:

每天一道算法_9_由后序遍历和中序遍历求前序遍历

 

 

 

最后得到的完整二叉树如下:

每天一道算法_9_由后序遍历和中序遍历求前序遍历

 

然后写出前序遍历就可以了,是ABDEGHJCFI

用算法可以实现的,暂时留在这。

 

 

作者:jason0539

微博:http://weibo.com/2553717707

博客:http://blog.csdn.net/jason0539(转载请说明出处)

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/121363.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • JS实现前进后退刷新的各种方法

    JS实现前进后退刷新的各种方法这里介绍了JS前进、后台、刷新的各种方法。也解释了很多前进后退函数出问题的原因。下面是用按钮做前进后退的JS:<inputtype=buttonvalue=刷新onclick=”window.location.reload()”/><inputtype=buttonvalue=前进onclick=”window.history.go(1)”/><inputtype=buttonvalue=后退onclick=”window.history.go(-

  • 智能小车资料源码大全下载_清翔智能小车资料

    智能小车资料源码大全下载_清翔智能小车资料今天给大家分享一下智能小车的资料,包括制作流程、原理图设计和源码等,不下于60辆智能小车的制作经验。其中历届智能小车的开发资料就有90个文件了。分享的智能小车类型包括:Bluetooth控制两轮小车;智能小车配套程序,循迹、红外避障综合程序资料大全;智能车系统解决方案;STM32两轮自平衡小车资料;STM32两轮自平衡小车系统毕设;自平衡小车控制(stc12+mpu6050程序);寻迹实验小车…

    2022年10月17日
  • java反射机制

    java反射机制学习spring提到spring框架中的setter方法是使用反射机制实现的,反射机制到底是什么呢?找了一篇文章Java基础与提高干货系列——Java反射机制Java基础与提高干货系列前言今天

  • Portraiture磨皮滤镜的使用,变美就这么简单

    Portraiture磨皮滤镜的使用,变美就这么简单欢迎关注公众号“游戏内圈”,免费更多领取资料:1、下载并解压安装包压缩包,然后将文件夹复制到PS安装的Plug-ins目录下。2、打开PS,进入主界面选择滤镜—永乐汉化—人像磨皮即可打开插件。3

  • IBM P750 AIX机器根目录空间满问题解决办法

    IBM P750 AIX机器根目录空间满问题解决办法今天有系统应用人员跟我讲数据库双机服务器空间快要满了,我登录到服务器上去查看发现根目录3G的空间只剩下不到一百多兆了,附图如下列出根目录下最占用空间的文件$du-amx/|sort-rn|head-n10关键字”/dev/null2>&1″,这是AIX6.1TL7中的cas_agent两个bug,关于这两个bug的英文介绍请移步http:/…

  • WES7下载_影音先锋下载

    WES7下载_影音先锋下载WES7(WindowsEmbeddedStandard7)是微软在2010年5月13日发布的基于X86平台,Windows7组件化的嵌入式操作系统。WES7除了具有Windows7最新的功能外,还具

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号