algorithm - 给定一个 preOrder 和 inOrder 序列，可能有多少级阶 BST 序列？

Question

当我尝试打印 BST 的级别顺序时，这个问题提示了我。

这是一个

Pre-Order Sequence: 4, 1, 2, 3, 5, 6, 7, 8
In_order Sequence : 1, 2, 3, 4, 5, 6, 7, 8

具有上述 pre_order 和 In_order 的 BST 的水平顺序序列是[4、2、6、1、3、5、7、8]

然而，对于相同的 Pre-order 和 In-order 序列，这种级别的顺序序列似乎是可能的。 [4、1、5、2、6、3、7、8]。我不知道怎么办。我正在努力解决这个问题。

我无法在满足所有 pre_order、In-order 和 level order 序列的纸(绘图)中构建 BST。

Answer 1

如果你有中序遍历和前序/后序之一，那足以重建一棵二叉树。此外，在 BST(二叉 搜索 树)的情况下，单独的后序或预序就足够了。

在您的例子中，从预购 4, 1, 2, 3, 5, 6, 7, 8 重构 BST 得到以下 BST:

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

这再次给出了唯一的级别顺序遍历 [4,1,5,2,6,3,7,8]。

另见:

• Reconstructing binary trees from tree traversals