如何在给定先序和中序遍历的情况下打印二叉树的后序遍历？

Question

当给定先序和中序遍历时，我被赋予了尝试打印二叉树的后序遍历的任务。

我上网搜索问题，但我找到的唯一结果是这篇GeekForGeeks文章。然而，我发现这篇文章很混乱，即使读完这篇文章我也不明白如何解决这个问题。有人可以帮助将文章简化为更简单的单词吗？谢谢！

Answer 1

这在一般情况下是不可能的。考虑：

  A
A   B

让我们将它们标记为

  1
2   3

• 预序遍历AAB(1,2,3)
• 中序遍历AAB(2,1,3)
• 后序遍历ABA(2,3,1)

现在考虑：

A (1)
  A (2)
    B (3)

• 预购：AAB (1,2,3)
• 顺序：AAB (1, 2, 3)
• 邮购：BAA (3, 2, 1)

给定预序树和中序树作为 AAB 将不会有明确的后序表示。