binary-tree - 查找仅给定中序遍历的二叉树

Question

我得到了一个中序遍历，需要找到一棵二叉树。我提到了我的网站，他们中的大多数人说这是不可能的。但是，我认为非唯一二叉树是可能的。我可以使用刚刚给定的中序遍历找到二叉树吗？如果没有，我可以从给定的中序遍历中找到相应的前序遍历吗？

我试图通过选择 in-order 的中心节点作为根来将 in-order 转换为 pre-order，但我不确定它是否正确。请指导我。

谢谢你。

Answer 1

仅给定节点的按序遍历，并且问题中没有更多信息，您可以找到二叉树，但正如您所说，不会有唯一的解决方案（特别是如果树不必是均衡）。结果，您可以再次找到预订遍历。

例如，如果您的中序遍历是[1,2,3,4,5,6,7,8]，那么即使树是平衡的，根节点也有多种可能性（即 4 或 5）。如果树不必平衡，您可以选择其中任何一个作为根节点。

这是一个非平衡树的示例，您可以在任意选择 4 作为根节点后构建：

      4
     /  \
    3    6
   /    / \
  2    5   7
 /          \
1            8

这棵树的前序遍历将产生4,3,2,1,6,5,7,8。同样，如果唯一的要求是您只找到一棵二叉树，这与将 1 设置为根节点并将其他所有内容设置为正确节点一样有效：

1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6
           \
            7
             \
              8

这棵树的前序遍历将是1,2,3,4,5,6,7,8。由于这些树都生成相同的有序遍历，但不同的前序遍历，因此对于给定的有序遍历，不能保证有一个唯一的树甚至是一个唯一的前序遍历。

Answer 2

对于多个节点，不存在包含中序遍历的唯一二叉搜索树。

但是如果你想要一棵树，那么只需对中序序列执行随机洗牌，然后将生成的随机序列插入二叉搜索树