Question

如何从后序遍历求原二叉树？

Answer 1

1、先求原始二叉树，后序遍历中最后出现的是根，所以A是整棵树的根，在结合中序遍历来看

BDCE是A的左子树，而FHG是A的右子树；

2、BDCE序列中B是整个序列根，因为后序遍历中B最后出现。此时再看中序中根B左端没有左子

树，右端有DCE,所以DCE是B的右子树 ；

3、再看D、C、E在后序遍历中C结点最后出现，所以C是根，此时再到中序遍历看可以看到C的左

端是D，右端是E，所以C的左子树是D，右子树是E；

4、再看F、H、G三个结点，后序遍历序列F最后出现，所以F是根结点，再回去看中序HG在F右

端，所以HG是F的右子树；

5、由于H、G在后序遍历序列G最后出现，所以G是H, G中的根，再看 中序中G左端只有一个H，

所以H是G的左子树，得到最终原始二叉树。

需要注意的几点：

1、根是相对的，对于整棵树而言只有一个根，但对于每棵子树而言，又有自己的根。

2、前序遍历时，一棵树的根永远在左子树前面，左子树又永远在右子树前面。

3、二叉树结点的先根序列、中根序列和后根序列中，所有叶子结点的先后顺序一样。