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

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。根节点右子节点是 6。最右边的节点是 5。

不幸的是，我不知道如何继续。任何提示将不胜感激。

Answer 1

从后序（LRN），我们知道最后一个元素是根。我们可以按顺序（LNR）找到根。然后我们可以按顺序识别根的左右子树。

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

检查此链接。