从两个遍历输出创建二叉树

Question

这是家庭作业，但由于某些原因，它不允许我添加作业标签。

我们被分配一个实验室的数据结构，其中最后一个问题问我们发现，会产生从给定的遍历方法如下输出二叉树：

LRN: 12, 9, 4, 7, 1, 14, 8, 13, 10, 15, 11, 2, 5, 16, 6, 3 

和

LNR: 12, 3, 4, 9, 8, 1, 7, 14, 6, 13, 10, 16, 5, 15, 2, 11 

我已经确定了以下关于该树的内容：

根节点是3.根节点离开孩子，只有树的左边孩子是12.根号des右边的孩子是6.最右边的节点是5.

不幸的是我被困在如何继续。任何提示将不胜感激。

Answer 1

从后序（LRN），我们知道最后一个元素是根。我们可以找到有序的（LNR）。然后，我们可以从有序的角度确定根的左右子树。

使用左侧子树的长度，我们可以在后序数组中识别左右子树。递归地，我们可以建立树。

检查this链接。