程序员经验分享-hwhale

二叉树系列(1)已知二叉树的中序遍历和前序遍历，如何求后序遍历

2023-11-09

一道HULU的笔试题(How I wish yesterday once more)

假设有棵树，长下面这个样子，它的前序遍历，中序遍历，后续遍历都很容易知道。


PreOrder:         GDAFEMHZ

InOrder:            ADEFGHMZ

PostOrder:       AEFDHZMG

 

现在，假设仅仅知道前序和中序遍历，如何求后序遍历呢？比如，已知一棵树的前序遍历是”GDAFEMHZ”，而中序遍历是”ADEFGHMZ”应该如何求后续遍历?

 

第一步，root最简单，前序遍历的第一节点G就是root。

 

第二步，继续观察前序遍历GDAFEMHZ，除了知道G是root，剩下的节点必然是root的左右子树之外，没法找到更多信息了。

 

第三步，那就观察中序遍历ADEFGHMZ。其中root节点G左侧的ADEF必然是root的左子树，G右侧的HMZ必然是root的右子树。

 

第四步，观察左子树ADEF，左子树的中的根节点必然是大树的root的leftchild。在前序遍历中，大树的root的leftchild位于root之后，所以左子树的根节点为D。

 

第五步，同样的道理，root的右子树节点HMZ中的根节点也可以通过前序遍历求得。在前序遍历中，一定是先把root和root的所有左子树节点遍历

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

DataStructureAlgorithm

c

struct

null

二叉树系列(1)已知二叉树的中序遍历和前序遍历，如何求后序遍历 的相关文章

随机推荐

  • 基于opencv实现人脸识别及签到系统

    首先需要安装opencv dlib face recongnition库 opencv安装起来比较简单 其他两个库的安装请看关于face recognition的安装最简单方式 时间和我都在往前走的博客 CSDN博客 这里代码可以直接用 不

  • UTC、RTC、UNIX时间戳、localtime 理解

    UTC RTC UNIX时间戳 localtime 理解 UTC 时间 UTC是世界协调时间时 UTC 是现在全球通用的时间标准 全球各地都同意将各自的时间进行同步协调 UTC 时间是经过平均太阳时 以格林威治时间GMT为准 地轴运动修正后

  • 集合框架（ ArrayList LinkedList）

    集合框架 存储多个数据 对象 使用数组 数组 存储相同数据类型一段连续的空间 限制 定长 添加 删除 统计比较麻烦 存储的是单列的值 学号 学生信息 订单号 订单详情 中文名称 英文名称 集合框架 一些接口和类 java util包 Col

  • 泛型反射，如何用泛型反射获得当前类泛型的具体类型

    有时候我们需要知道当前类所传入的泛型的具体类型而进行下一步操作 这是我们可以使用泛型反射 1 假如Dao层的接口有很多共同的方法 增删改查 我们可以对他进行提取到一个公共接口IBaseDao

  • 地质灾害监测的主要内容

    地质灾害就地质环境或地质体变化的速度而言 可分为突发性地质灾害与缓变性地质灾害两大类 其中崩塌 滑坡 泥石流是地质灾害的主要表现形式 我国是地质灾害多发的国家 全国共有较大型崩塌3000多处 滑坡2000多处 泥石流2000多处 中小规模的

  • 通过JavaAPI访问HBase

    先开始创建表 create emp001 member id address info 放入数据 put emp001 Rain id 31 put emp001 Rain info birthday 1990 05 01 put emp0

  • 九、1~8文章的阶段案例

    一 案例 现在我们来做一个相对综合一点的练习 书籍购物车 案例说明 1 在界面上以表格的形式 显示一些书籍的数据 2 在底部显示书籍的总价格 3 点击 或者 可以增加或减少书籍数量 如果为1 那么不能继续 4 点击移除按钮 可以将书籍移除

  • 最大权值闭合子图的证明详解

    前面定义部分转自这篇博客 网络流 最小割求最大权闭合子图 定义 有一个有向图 每一个点都有一个权值 可以为正或负或0 选择一个权值和最大的子图 使得每个点的后继都在子图里面 这个子图就叫最大权闭合子图 能选的子图有 4 3 4 2 4 1

  • CocosCreator ios 使用sdl库找不到arm64指令集

    关于sdl如何打包成ios库 android库的问题 之后会有相关文章介绍 现在先说一下CocosCreator在使用xcode运行过程中 会报的一个错 Undefined symbols for architecture arm64的错误

  • Android墓碑以及ANR跟踪文件路径

    ANR data anr 墓碑 data tombstones

  • Hadoop-3.2.3集群搭建

    Hadoop 3 2 3集群搭建 一 准备工作 准备三台最小化安装的Linux服务器 单节点伪集群一台虚拟机即可 hdfs配置副本数设置为1 worker只有一个 ipaddress hostname 192 168 116 10 hado

  • 华为2288H-V5 组RAID安装系统（描述安装系统）

    先说下兼容性我这里是bios是最新的19版 和17版有些许差异 windows方面不支持windows2012以下的版本 2008R2再见 linux方面支持常用的linux系统如红帽6 9 6 10 7 4以上系统 7 0 7 3这些不支

  • k8s与log--利用fluent bit收集k8s日志

    前言 收集日志的组件多不胜数 有ELK久负盛名组合中的logstash 也有EFK组合中的filebeat 更有cncf新贵fluentd 另外还有大数据领域使用比较多的flume 本次主要说另外一种 和fluentd一脉相承的fluent

  • 如何更新R

    更新R版本 1 直接安装install packages installr 然后 library installr 再updateR 2 把原来的R删掉 再到官网下载 The R Project for Statistical Comput

  • Java中变量详解（类的五成员之一：变量）

    目录 友情提醒 概述 Java中的成员包含五部分 第一部分 变量 1 Java中的变量分类 2 成员变量和局部变量的位置区别 3 Java中成员变量作用域 Java权限修饰符 4 Java中成员变量和成员属性的区别 5 成员变量初始化方式

  • Numbers on Whiteboard （codeforces1430）（数学分析）

    Numbers 1 2 3 each integer from 1 to once are written on a board In one operation you can erase any two numbers and from

  • LeetCode 刷题记录14. 最长公共前缀

    题目描述 编写一个函数来查找字符串数组中的最长公共前缀 如果不存在公共前缀 返回空字符串 说明 示例 1 输入 strs flower flow flight 输出 fl 示例 2 输入 strs dog racecar car 输出 解释

  • 修改网页logo图片

    在html的head代码区加入以下代码 保存刷新页面即可

  • Lua基础之字符串（string）

    1 计算字符串长度 2 返回字符串s的n个拷贝 3 返回字符串全部字母大写 4 返回字符串全部字母小写 5 返回一个类似printf的格式化字符串 6 根据下标截取字符串 7 在字符串中查找 8 在字符串中替换 9 返回字符的整数形式 10

  • 二叉树系列(1)已知二叉树的中序遍历和前序遍历，如何求后序遍历

    一道HULU的笔试题 How I wish yesterday once more 假设有棵树 长下面这个样子 它的前序遍历 中序遍历 后续遍历都很容易知道 PreOrder GDAFEMHZ InOrder ADEFGHMZ PostOr

热门标签