algorithm - 从其前序和后序列表中重建一棵树

Question

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

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

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

---

注意:所讨论的树可能不是二元的，也不是平衡的，或者任何会使它变得太简单的东西。

注2:只使用前序或后序列表会更好，但我认为这是不可能的。

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

注4:我只关心 sibling 的顺序。当只有一个 child 时，左或右并不重要。

Answer 1

Preorder and postorder do not uniquely define a tree.

In general, a single tree traversal does not uniquely define the structure of the tree. For example, as we have seen, for both the following trees, an inorder traversal yields [1,2,3,4,5,6].

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

The same ambiguity is present for preorder and postorder traversals. The preorder traversal for the first tree above is [4,2,1,3,5,6]. Here is a different tree with the same preorder traversal.

    4
   / \
  2   1
     / \
    3   6
     \
      5

Similarly, we can easily construct another tree whose postorder traversal [1,3,2,6,5,4] matches that of the first tree above.