Ocaml帮助树遍历

Question

问题描述：

鲍里斯特教授研究树木。他记录了所有他喜欢的树的前序、序和后序遍历。然而，他办公室的一场火灾摧毁了他存放有序遍历的文件柜。他仍然拥有他最喜欢的所有树的前序和后序遍历，这些信息足以重建丢失的按序遍历吗？

您必须为以下任务设计和实现一个程序：输入将由两个数字列表组成。第一个列表是一些树T的前序遍历。第二个列表是同一棵树T的后序遍历。输出应该是T的无序遍历。如果输入没有确定唯一的树，那么任何一致的无序遍历都可以返回。

如果它有助于设计实现，您可以假设：

• 没有树有超过1000个节点。
• 没有树对多个节点使用相同的标签。
• 节点的标签是从0到10000的数字。

样本数据

Input:
2 6 7 1 11 8 5 10 3 4 9
7 8 5 11 10 1 6 4 9 3 2
Output:
7 6 8 11 5 1 10 2 4 3 9

提示

按预定顺序

首先解决当树中的每个节点都保证有2个或0个子节点时的问题。有些节点只有一个子节点的情况有点棘手。

笔记

在您的写作中，您不需要分析解决方案的效率/运行时间（这将是未来项目的要求）。但是一定要分析它的正确性；也就是说，清楚地解释为什么你的算法是正确的。

Answer 1

即使问题描述没有明确地这样说，从提示中可以清楚地看出，我们正在处理二叉树。

提示很好：找到树的根，然后找到左子树的根和右子树的根。

删除根后，在节点列表中寻找可以剪切列表的位置：剪切前的节点来自左侧子树，剪切后的节点来自右侧子树。

像你那样做一些小例子是个好主意。

具体回答“理解如何从pre和post构建索引遍历”：首先从pre和post遍历重建树，然后从树构建索引遍历。