我发现如果我们有 Preorder 和 Inorder Traversal，我们就有了一棵独特的树。
我可以得出结论：
对于每个 Preorder Traversal，我们有多个 Inorder Traversal。这是对还是错的结论？每个人都会帮助我并添加一些细节。
再次感谢。
user3691721
问问题
245 次
2 回答
0
是的，因为您可以从单个预购序列中创建多棵树。例如： [4,3,1, 2] 可以表示为具有根 4、子节点 3 和 2 的树。然后您可以将 1 作为 3 的左子节点或右子节点插入。取决于您将插入它的位置顺序会改变。
你也可以这样推理：你有n 个数字，用它们你可以得到n！排列。如果排列的数量等于您可以使用这n 个数字创建的可能树的数量，则可以从您的遍历中生成一棵树。情况并非如此，尽管您可以例如创建许多树，其中每个节点只有一个左孩子或只有一个右孩子，这给了您 2*n！而且还有更多，所以必须有一个可以生成超过 1 个树 => 超过 1 个中序遍历的排列。
这在一般情况下当然是正确的，BST 具有唯一的中序序列。
于 2014-09-05T06:23:15.563 回答
0
真的，例如：给定一个前序遍历 abdec
a
/ \
b c
/ \
d e
许多中序遍历是可能的：baedc、dbeac 等等......
于 2014-09-05T06:27:06.440 回答