题目

二叉树的先序、中序和后序序列 请构造出该二叉树
已知一棵二叉树的先序、中序和后序序列如下,其中各有一部分未给出其值,请构造出该二叉树
先序序列 ：A _ C D E F_ H _ J
中序序列 ：C _ E D A _ G F I _
后序序列 ：C _ _ B H G J I _ _
关键是想看过程

提问时间：2021-01-23

答案

先序的第一个为二叉树树根A,因此后序的最后一个也是A
回到中序,以A为根划分,左子树有4个结点,右子树有5个结点
现在看后序：前4个最后的是B,因此先序的第二个是B,并且中序的第二个也是B
简化如下：
先序序列 ：A B C D E F_ H _ J
中序序列 ：C B E D A _ G F I _
后序序列 ：C _ _ B H G J I _ A
回到先序,A后面连续4个为左子树的先序,因此后面的F就是右子树的根
因此后序的倒数第2个就是F
再利用先序的DE和中序的ED可以得到后序为ED
于是再次简化为：
先序序列 ：A B C D E F _ H _ J
中序序列 ：C B E D A _ G F I _
后序序列 ：C E D B H G J I F A
现在来看右子树：已知右子树的根为F
从中序可知,F有左右子树,且左右均为2个结点,
从后序序列可知其前的I就是右子树的根,因此,先序J前面的就是I,并且中序最后的就是J
剩下的就可以补充完整了（其实用二叉树的遍历序列也可硬性推导出）
最后结果是：
先序序列 ：A B C D E F G H I J
中序序列 ：C B E D A H G F I J
后序序列 ：C E D B H G J I F A