算法通关村——如何使用中序和后序来恢复一棵二叉树
通过序列构造二叉树
给出以下三个二叉树遍历的序列：
(1) 前序: 1 2 3 4 5 6 8 7 9 10 11 12 13 15 14
(2) 中序: 3 4 8 6 7 5 2 1 10 9 11 15 13 14 12
(3) 后序: 8 7 6 5 4 3 2 10 15 14 13 12 11 9 1
前中序复原二叉树
所需序列
(1) 前序: 1 2 3 4 5 6 8 7 9 10 11 12 13 15 14
(2) 中序: 3 4 8 6 7 5 2 1 10 9 11 15 13 14 12
左子树复原
第一轮
通过前序： 前序第一个访问的是根节点，因此根节点就是1
通过中序：中序遍历的特点就是根节点的左子树的元素都在根节点的左侧，右子树的元素都在根节点的右侧，从中序遍历序列结合前序序列可知，中序序列1的左侧为左子树，1的右侧为右子树。从而前序通过中序划分可知，前序的左右子树。划分如下：
中序序列划分： [3 4 8 6 7 5 2] 1 [ 10 9 11 15 13 14 12]
前序序列划分: 1 [2 3 4 5 6 8 7 ] [9 10 11 12 13 15 14]
分析
如何知道两个括号从哪里分开？可参照中序的两个数组划分的。
前序中 7 之前的元素都在中序第一个数组中，9之后的所有元素都在第二个数组中，因此从7和9之间划分。
第一轮划分结果如下图
第二轮
我们先看前序和中序的第一个数组
前序: 2 3 4 5 6 8 7中序: 3 4 8 6 7 5 2
通过上面的结论可知：
根节点为2（前序）
然后可划分为：
前序: 2 [3 4 5 6 8 7 ]
中序: [3 4 8 6 7 5 ] 2
第二轮划分结果如下图
第三轮
对 3 4 5 6 8 7 继续划分：
前序: 3 [4 5 6 8 7]
中序: 3 [4 8 6 7 5]
第三轮划分结果如下图
第四轮
对 4 5 6 8 7 进行划分：
前序：4 [5 6 8 7]
中序：4 [ 8 6 7 5 ]
第四轮划分结果如下图
第五轮
对 5 6 8 7 划分：
前序：5 [6 8 7]
中序：[8 6 7] 5
第六轮
对 6 8 7 划分
前序：6 [ 8 7 ]
中序： [8] 6 [7]
至此，便可知左子树的树结构了。
左子树的树结构效果如下：
左子树的复原结果如下
右子树复原
第一轮
由第一轮可知如下序列
前序： 9 10 11 12 13 15 14
中序： 10 9 11 15 13 14 12
对其进行划分，结果如下
前序：9 [ 10 11 12 13 15 14]
中序：[10] 9 [11 15 13 14 12]
由结果可知，10 是 9 的左子树，11 15 13 14 12为还需划分的序列
第二轮
将序列11 12 13 15 14进行划分：
前序：11 [12 13 15 14]
中序：11 [15 13 14 12]
第三轮
将12 13 15 14进行划分：
前序：12[13 15 14]
中序： [15 13 14]12
第四轮
将 13 15 14进行划分：
前序：13 [ 15 14]
中序： [15] 13 [14]
最终由中序获得结果，15为13的左子树，14为13的右子树
左右子树复原结果如下
中后序恢复二叉树
通过中后序恢复二叉树与前中序唯一的不同就是：后续的最后一个是根节点，中序的处理和上述相同。所需序列如下：
(2) 中序: 3 4 8 6 7 5 2 1 10 9 11 15 13 14 12
(3) 后序: 8 7 6 5 4 3 2 10 15 14 13 12 11 9 1
左子树复原
第一轮
中序序列划分：[3 4 8 6 7 5 2] 1 [10 9 11 15 13 14 12]
后序序列划分：[8 7 6 5 4 3 2 ] [10 15 14 13 12 11 9 ]1
由于上述经过了上述分析，对划分结果有所了解了，因此此次划分就不画中间过程了
第二轮
对序列 8 7 6 5 4 3 2 进行划分
中序：[3 4 8 6 7 5 ] 2
后序：[8 7 6 5 4 3 ] 2
第三轮
对序列 8 7 6 5 4 3 进行划分:
中序：3[4 8 6 7 5]
后序：[8 7 6 5 4] 3
第四轮
对序列8 7 6 5 4进行划分：
中序：4 [8 6 7 5]
后序：[8 7 6 5] 4
第五轮
对序列8 7 6 5进行划分：
中序：[8 6 7 ] 5
后序：[8 7 6 ] 5
第六轮
对序列 8 7 6进行划分：
中序：[8] 6 [7]
后序：[8 7] 6
最终，由中序划分可知，8是6的左子树，7是6的右子树
左子树复原结果如下
右子树复原
右子树复原所需要的序列：
中序：10 9 11 15 13 14 12
后序：10 15 14 13 12 11 9
第一轮
将序列10 15 14 13 12 11 9进行划分（一般选择能确定根节点的那个节点）：
中序：[10] 9 [11 15 13 14 12]
后序：[10 15 14 13 12 11] 9
由此划分可知，10为9的左节点，11 15 13 14 12为9的右子树
第二轮
对序列15 14 13 12 11进行划分：
中序：11 [15 13 14 12]
后序：[15 14 13 12] 11
第三轮
对序列15 14 13 12进行划分：
中序：[15 13 14] 12
后序：[15 14 13] 12
第四轮
对序列15 14 13 进行划分：
中序：[15] 13 [14]
后序：[15 14]13
从中序结果可知，15为13的左子树，14为13的右子树
左右子树复原结果如下
由此可知，前中序和中后序恢复成 二叉树的过程有些不同，但是所需的步骤和结果都是一致的。
知道了序列是如何构造成二叉树之后，便可以将其使用代码实现了，代码实现在下次总结。