从前序和后序列表重建树

考虑这样一种情况，您有两个节点列表，您只知道其中一个是某棵树的前序遍历的表示，另一个是同一棵树的后序遍历的表示。

我相信可以从这两个列表精确地重建树，并且我认为我有一个算法可以做到这一点，但尚未证明。由于这将是硕士项目的一部分，我需要绝对确定它是可能的且正确的（经过数学证明）。然而，这不是该项目的重点，所以我想知道是否有可以引用的来源（即论文或书籍）作为证明。 （也许在 TAOCP 中？有人可能知道这个部分吗？）

简而言之，我需要在可引用资源中提供一种经过验证的算法，该算法可以根据前后顺序遍历来重建树。

注意：所讨论的树可能不是二元树，也不是平衡树，也不是任何使它变得太容易的树。

注2：仅使用预购或后购列表会更好，但我认为这是不可能的。

注3：一个节点可以有任意数量的子节点。

Note4：我只关心兄弟姐妹的顺序。当只有一个孩子时，左或右并不重要。

前序和后序并不唯一地定义一棵树。 http://www.cmi.ac.in/~madhavan/courses/programming06/lecture12-21sep2006.txt

一般来说，单个树的遍历并不能唯一地定义 树的结构。例如，正如我们所见，对于两者 以下树，中序遍历得到 [1,2,3,4,5,6]。

    4                     3
   / \                   / \
  2   5                 2   5
 / \   \               /   / \
1   3   6             1   4   6

预购和后购也存在同样的歧义 遍历。上面第一棵树的前序遍历是 [4,2,1,3,5,6]。这是具有相同预序的不同树 遍历。

    4
   / \
  2   1
     / \
    3   6
     \
      5

类似地，我们可以轻松构造另一棵树，其后序 遍历 [1,3,2,6,5,4] 与上面第一棵树的遍历相匹配。