algorithm - 预序和与中序遍历的关系

Question

我发现如果我们有先序遍历和中序遍历，我们就有了一棵唯一的树。

我可以得出结论吗:

对于每个前序遍历，我们有多个中序遍历。这是对还是错的结论？每个人都会帮助我并添加一些细节。

再次感谢。

Answer 1

是的，因为您可以从单个预购序列创建多棵树。例如:[4,3,1,2] 可以表示为根为 4、子节点为 3 和 2 的树。然后您可以将 1 作为 3 的左子节点或右子节点插入。取决于您将插入它的位置，中序顺序会改变。

你也可以这样推理:你有 n 个数，用它们你可以得到 n! 个排列。如果排列数等于您可以使用这些 n 数创建的可能树的数量，则可以通过遍历生成树。情况并非如此，尽管你可以创建许多树，其中每个节点只有一个左 child 或只有一个右 child ，这给你 2*n!而且还有更多，所以必须有一个排列可以生成多于 1 棵树 => 多于 1 次中序遍历。

这在一般情况下当然是正确的，BST 具有唯一的有序序列。