data-structures - 给定前序和后序遍历时，为什么不能确定树的中序遍历？

Question

我们都熟悉二叉树的前序、中序和后序遍历。数据结构类中的一个常见问题是：

• 当给定中序和后序遍历时，找到二叉树的前序遍历。
• 或者，您可以在给定中序和预序时找到后序遍历。
• 但是，一般来说，当给定树的前序和后序遍历时，您无法确定树的中序遍历。

我想知道为什么，有没有一种从理论上解释它的好方法？

更新 1 一个答案：父母只有 1 个孩子的叶子会有问题，因为在这种情况下，这样的叶子可以是左孩子或右孩子。

Answer 1

我不熟悉对此的理论解释，但我会尝试从逻辑上解释它。

让我们考虑一个更一般的问题：- 使用前序和后序遍历构造二叉树。

让我们举个例子。我们有以下树：

    1
   / \
  2   5
 / \   \
3   4   6

这棵树的前序为 (1,2,3,4,5,6)，后序为 (3,4,2,6,5,1)。现在，我们希望重建同一棵树。

我们知道 1 是根节点。现在我们转到 2。在后序中，因为 2 在 1 之前，所以它是 1 的子节点。3 在下一个。由于 3 在 2 之前，它是 2 的孩子。 4 在 2 之前，因此它是孩子。5 在 2 之后但在 1 之前，所以它是 1 的孩子，但不是 2。6 同样是 5 的孩子。但是 6 是左孩子还是右孩子？我们这里有两种可能：

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

无法确定 6 是 5 的左孩子还是右孩子。如果是 2（和类似的 1）孩子，我们可以肯定，因为在后序遍历（左树、右树、 root) 但如果是单个孩子，则存在歧义。

因此，对于不完整的二叉树，不能明确地确定树并因此确定中序遍历（尽管如果树是完整的则可以）。