algorithm - 从给定的遍历中构建二叉树

Question

我正在解决我遇到这个问题的数据结构和算法课程的作业：

“给定两种遍历方法，可以是前序和后序，前序和中序，后序和中序，我们可以提取多少二叉树？”

现在我知道你肯定不能只从一个遍历顺序中找到二叉树，但是这两个遍历中的哪一个只会给你一棵二叉树？如何 ？以及那些没有举例说明一棵二叉树的例子，他们举例说明了多少二叉树，我们如何计算这个数字？

Answer 1

我相信这个来源很有用。树的前序和后序遍历不足以在没有进一步限制的情况下唯一地重建它。然而，一个算法展示了如何从它的后序和中序遍历重建一棵树，并且由于最后一种情况有点对称，我相信这是算法证明可以从它的中序和任何其他遍历中唯一地重建一棵树。