已知一棵树的前序序列为ABCDEF，后序序列为CEDFBA，则对该树进行层次遍历得到的序列为?

Question

遇见已知先序后序这类问题如何解决?感觉没有中序很难0.0求大神~!

Answer 1

首先，先明确，题目中说的是树的遍历，而不是二叉树的遍历。如果是二叉树，是无法通过前序遍历和后续遍历推出一个确定的树的。
树的前序遍历相当于二叉树的前序遍历，树的后序遍历相当于二叉树的中序遍历，由此，我们能推出一个确定的二叉树。这里完成了第一步。
第二步，需要将二叉树的还原成普通的树， （若某结点是其双亲的左孩子，则把该结点的右孩子、 右孩子的右孩子……都与该结点的双亲结点用线连起来）。
得到原始树的结构，如图，最后自上向下，自左向右的层次遍历，得到ABCDFE。