摄影:产品经理与产品经理环游世界偶遇的早餐店的麦片
我们知道,二叉树有三种不同的遍历方式:先序遍历
,中序遍历
和后序遍历
。这三种遍历方式本质上是根据根节点的位置来命名的。根节点在前面,就是先序遍历;根节点在中间,就是中序遍历;根节点在最后,就是后续遍历。
例如,对于下图所示的二叉树:
先序遍历就是: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
和它右边的元素,就是先序遍历中对应到右支树的部分。
总结下来,就是:
- 从先序遍历剩下的元素中的第一个元素确定根节点
- 用根节点到后续遍历中分割左右支树的元素。
- 从先序遍历中,剔除第2部获取的左支树的部分,剩下的就是右支树的部分
- 重复
根据这一点,我们可以看到,先序遍历中间的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、7
的2
是左支树的根节点。我们在后序遍历中找到它。于是可以知道,左支树只有4、2
两个节点,右支树有3、5、6、7
4个节点:
我们先来看左支树先序2、4
,说明2
是根节点。把2
放到后序遍历4、2
中。现在可以知道,4
是2
的叶子节点,但不知道是左还是右:
再来看右边的情况。先序遍历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。请大家在评论中给出后续遍历。