data-structures - 证明具有相同中序和前序遍历的二叉树是相同的吗？

标签 data-structures binary-tree

有谁知道怎么办证明如果两棵二叉树具有相同的中序和前序遍历，那么它们是相同的吗？ (也许通过表明你不能有两个不同的二叉树具有相同的中序和前序遍历)

或者，展示一个可以反驳这一点的案例，或者展示为什么不能这样做？

(我承认，这纯粹是学术性的，但不是家庭作业或其他任何东西。我的直觉告诉我这是真的，但我认为我从未对图表做过任何证明。)

最佳答案

基本思想是如何通过给定的中序和前序遍历来重建二叉树。

可以重建只有一个 中序遍历和前序遍历生成二叉树。

看:

Nonrecursive algorithms for reconstructing a binary tree from its traversals (纸)

reconstructing a tree from its preorder and postorder lists (SO 问题)

关于data-structures - 证明具有相同中序和前序遍历的二叉树是相同的吗？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/1558032/