我们可以从中序序列构造BST吗？

Question

我们可以从 preOrder 或 postOrder 序列构造二叉搜索树 (BST)。但是我们可以仅从中序序列构建 BST 吗？我认为使用 inOrder 序列构建 BST 是不可能的，因为我们找不到它的根元素。

Answer 1

你是对的。两个不同的二叉搜索树可以具有相同的有序序列，因此您不知道选择哪一棵。然而，如果可以选择任何具有该有序序列的 BST，那么这是可能的。

但我猜你的问题是关于重建与派生中序序列的树相同BST。 这是不可能的：通过将 BST 转换为中序序列，您会丢失信息。即使您将根作为“附加”信息提供给您，您通常也无法做到这一点。事实上，在给定数量的节点下，BST 的形状可以是任何可能的形状。 最小的例子是 inorder [1, 2]。它可以代表这两棵树：

           2           1
          /             \
         1               2

如果在这种情况下您获得了根作为额外信息，那么当然可以从中导出 BST。下一个最小的例子：[1,2,3]。这些树都具有中序序列：

          3           2            1
         /           / \            \
        2           1   3            2
       /                              \
      1                                3

同样，如果您获得根作为额外信息，您将能够知道三个 BST 中哪一个是正确的。但是一旦我们得到更大的树，即使我们得到了根，我们也并不总是能够知道正确的 BST。

还请注意，BST 并不

有

达到最佳平衡。但即使我们只考虑最优平衡 BST，中序序列也不能唯一地定义树。上面有 2 个节点的示例已经证明了这一点。但让我们看一下中序序列为 [1, 2, 3, 4] 的四个节点。具有该有序序列的最平衡树是：

        3             3            2          2
       / \           / \          / \        / \
      2   4         1   4        1   4      1   3
     /               \              /            \
    1                 2            3              4
        

在这里我们还看到，如果给定最优平衡 BST 的根，仍然存在两种可能性。