专栏首页未闻Code如何根据二叉树的两种遍历方式重建二叉树(理论篇)

如何根据二叉树的两种遍历方式重建二叉树(理论篇)

摄影:产品经理

与产品经理环游世界偶遇的早餐店的麦片

我们知道,二叉树有三种不同的遍历方式:先序遍历中序遍历后序遍历。这三种遍历方式本质上是根据根节点的位置来命名的。根节点在前面,就是先序遍历;根节点在中间,就是中序遍历;根节点在最后,就是后续遍历。

例如,对于下图所示的二叉树:

先序遍历就是:8、3、1、1、2、5、13,中序遍历就是:1、1、2、3、5、8、13,后续遍历就是:1、2、1、5、3、13、8

对于一个普通的二叉树,如果只给出一种遍历方法,是没有办法重建二叉树的,因为不同的二叉树的某种遍历方式可能相同。

例如对于中序遍历1、1、2、3、5、8、13,也适用于下图所示的二叉树:

但如果给出两种遍历方式,就有 的概率可以唯一确定一颗二叉树。

先序遍历+中序遍历

给出先序遍历8、3、1、1、2、5、13和中序遍历1、1、2、3、5、8、13,如何重构?

先序遍历中,第一个元素是根节点。中序遍历中,根节点左边是左支树,根节点的右边是右支树。所以,我们首先可以得出如下的粗略结果:

其中,左支树目前还不清楚具体如何排列,只知道它的中序遍历是1、1、2、3、5。此时,我们回到先序遍历中,可以知道,左支树的先序遍历是3、1、1、2、5。重复刚才的分析方法。左支树先序遍历的第一个元素3就是左支树的根节点。中序遍历中,左支树的根节点左边的元素就是左支树的左支树,右边的元素就是左支树的右支树,于是二叉树进一步完善:

重复相同的方法,我们最终就能得到原来的二叉树:

后续遍历+中序遍历

给出中序遍历:1、1、2、3、5、8、13,后续遍历:1、2、1、5、3、13、8,如何重构?

方法与先序遍历+中序遍历完全一样,只不过这次,后序遍历的最后一个元素是根节点,有了根节点以后,从中序遍历中在根节点左边的就是左支树;在根节点右边的就是右支树。

从图中可以看出,右支树只有一个节点,所以我们继续从后续遍历里面移除13。于是左支树对应的后续遍历是1、2、1、5、3,对应的中序遍历是1、1、2、3、5,说明根节点是3

重复上面的步骤,最终得到结果。

先序遍历+后续遍历

给定先序遍历:8、3、1、1、2、5、13,后续遍历:1、2、1、5、3、13、8,如何重构?

这看起来似乎是最难的组合,因为从先序遍历的第一个元素和后续遍历的最后一个元素知道,根节点是8.但先序遍历的左右支树混在了一起3、1、1、2、5、13,哪几个元素是左支树,哪几个元素是右支树?对后续遍历也有这个问题。

但实际上这个问题也很好解决。我们把先后两种遍历方式移除根节点以后,上下对比:

3、1、1、2、5、13
1、2、1、5、3、13

无论内部顺序如何,由于先序遍历是根左右,后续遍历是左右根,所以移除根节点以后,必定剩下左右。既然如此,先序遍历对应到左支树的部分,必定与后续遍历对应到左支树的部分具有相同的元素,只不过顺序可能不同。我们首先从先序遍历剩下的元素中,找到第一个元素3,它应该是左支树的根节点(如果有左支树的话,稍后我们会说没有左支树的情况),我们在后序遍历中也找到这个数字3,此时,这个3和它左边的数据,就是后续遍历的左支树,这个3右边的数据13就是后续遍历中的右支树。我们再根据这个13回到先序遍历中,先序遍历中的13和它右边的元素,就是先序遍历中对应到右支树的部分。

总结下来,就是:

  1. 从先序遍历剩下的元素中的第一个元素确定根节点
  2. 用根节点到后续遍历中分割左右支树的元素。
  3. 从先序遍历中,剔除第2部获取的左支树的部分,剩下的就是右支树的部分
  4. 重复

根据这一点,我们可以看到,先序遍历中间的3、1、1、2、5对应左支树,剩下的13对应右支树.

于是,我们初步恢复的二叉树如下图所示:

重复这个步骤,得到第二层的结果:

重复上面的过程,得到最终结果。

我们再来看一个更复杂的情况:先序遍历为:1、2、4、3、5、6、7,后序遍历为:4、2、5、7、6、3、1

还是按我们上面讲到的方法,首先先序遍历的第1位和后序遍历的最后一位确定根节点1

先序遍历剩下的2、4、3、5、6、72是左支树的根节点。我们在后序遍历中找到它。于是可以知道,左支树只有4、2两个节点,右支树有3、5、6、74个节点:

我们先来看左支树先序2、4,说明2是根节点。把2放到后序遍历4、2中。现在可以知道,42的叶子节点,但不知道是左还是右:

再来看右边的情况。先序遍历3、5、6、7说明3是根节点。先序的左右对应5、6、7说明5是左支树的根节点。把5放到后续遍历的结果中,发现5左边没有数据,说明左支树只有5。于是得到如下一个粗略的二叉树:

剩下先序7、6和后序6、7知道6是根节点,7是叶子节点,但也不知道左还是右:

从这个例子可以看出,先序遍历+后续遍历,不一定能唯一确定一颗二叉树。

总结

二叉树有三种遍历方式,中序遍历+另外任意一种遍历方式,可以唯一确定一颗二叉树。先序遍历与后续遍历不一定能唯一确定一个二叉树。

在上面的例子里面,我使用的是数字来表示,相当于二叉树里面每个节点的值。但在计算机中,如果要给出两种遍历方式,一般是给出每个节点的对象列表或者地址列表。如果给出值一定每个值都不一样。不会出现先序遍历1、1、1、1、1、1、1中序遍历1、1、1、1、1、1、1让你还原二叉树的沙雕题目。

最后给大家出个题目:

有一颗二叉树,先序遍历:1、2、4、6、5、7、8、9、3、10、11、12,中序遍历:6、4、2、7、5、8、9、1、11、10、12、3。请大家在评论中给出后续遍历。

本文分享自微信公众号 - 未闻Code(itskingname),作者:kingname

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-04-11

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 一日一技:用Python反重力

    青南
  • 一日一技:使用下划线代替没有使用的循环计数变量

    根据Python的PEP8编码规范,对于用不到的循环计数变量,应该使用下划线代替。例如:

    青南
  • 在 Linux/Mac 下为Python函数添加超时时间

    我们在使用 requests 这类网络请求第三方库时,可以看到它有一个参数叫做timeout,就是指在网络请求发出开始计算,如果超过 timeout 还没有收到...

    青南
  • 图的深度遍历和广度遍历

    图的深度遍历和广度遍历都不算很难像极了二叉树的前序遍历和层序遍历,如下面的图,可以用右边的邻接矩阵进行表示,假设以顶点0开始对整幅图进行遍历的话,两种遍历方式的...

    233333
  • 遍历

    前序遍历(DLR),是二叉树遍历的一种,也叫做先根遍历、先序遍历、前序周游,可记做根左右。前序遍历首先访问根结点然后遍历左子树,最后遍历右子树。

    Centy Zhao
  • 5.2二叉搜索树遍历(前序、中序、后序、层次、广度优先遍历)

    前言:在上一节中,我们对树及其相关知识做了了解,对二叉搜索树做了基本的实现,下面我们继续完善我们的二叉搜索树。

    wfaceboss
  • 二叉树---(3)前序遍历,中序遍历,后序遍历

            很多朋友在刚开始接触二叉树时,对前序遍历,中序遍历,后序遍历这三个遍历方式不太了解,很多博客中,上来就是实现方式,并没有清晰的阐述这三种遍历的步...

    IT云清
  • 爬虫课程(四)|深度优先和广度优先算法

    黄小怪
  • 二叉树的遍历回顾

    本文重点在于复习并总结 二叉树每种遍历方式的递归与迭代实现,图片和示例代码均来自《邓俊辉-数据结构》。

    李拜六不开鑫
  • 根据先序和中序输出后序遍历

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    喜欢ctrl的cxk

扫码关注云+社区

领取腾讯云代金券