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

一个 BST 的水平顺序序列与上面pre_order和In_order是 [4, 2, 6, 1, 3, 5, 7, 8]

然而，对于同一个预购顺序，这个级别顺序顺序似乎是可能的。[4, 1, 5, 2, 6, 3, 7, 8]. 我不知道怎么做。我试图弄清楚这一点。

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

Answer 1

如果您有顺序遍历以及前/后顺序之一，则足以重建二叉树。此外，在 BST（二叉搜索树）的情况下，仅后序或前序就足够了。

在您的情况下，从预购中重建 BST4, 1, 2, 3, 5, 6, 7, 8会得到以下 BST：

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

这再次给出了唯一的 level-order traversal [4,1,5,2,6,3,7,8]。

也可以看看：

• 从树遍历重建二叉树

Answer 2

以下组合将生成唯一的二叉树（可以是 BST）。

Inorder and Preorder.
Inorder and Postorder.
Inorder and Level-order.

因此，在您的情况下，给出了 inorder 和 pre order，这将生成唯一的二叉树，在您的情况下是 BST，因此该树的级别顺序将是唯一的。

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

SO树将是

level 0- 4
level 1- 1,5
level 2- 2,6
level 3- 3,7
level 4- 8

水平顺序是

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

在排序中总会有唯一的级别顺序遍历