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

摄影：产品经理

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

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

例如，对于下图所示的二叉树：

先序遍历就是：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、7的2是左支树的根节点。我们在后序遍历中找到它。于是可以知道，左支树只有4、2两个节点，右支树有3、5、6、74个节点：

我们先来看左支树先序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。请大家在评论中给出后续遍历。