从级序遍历输出构造唯一的二叉搜索树

Question

我们可以使用前序遍历输出构造唯一的二叉查找树，如下所示：

1. 第一个元素将是根。
2. 左子元素=小于根的最近元素。
3. 右子元素=最近的元素大于根。

这些事实很容易转换成代码。然而，我正在努力获得如此严格的事实/步骤，以将级别顺序遍历输出转换为唯一的二叉查找树。

例如，如果我有以下级别顺序遍历输出[5,4,8,1,7,2,6,3]，我可以形成BST如下：

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

级别顺序遍历中的第一个元素始终是根（级别0）。然后是级别1的元素。4小于5，所以我将把它作为左子pf 5。8大于5，所以我将把它作为5的正确孩子。（它不能是4岁的孩子，因为在这种情况下，它应该小于5岁。因此它不能出现在2级）。然后是1和7。1应该是4的孩子，因为它小于4。7不能是4的正确子级，因为它也大于5。所以它应该在5的右子树上。因此，它必须是8岁的孩子，就像7岁一样

我觉得这是正常的BST创作。也就是说，它是通过按级别顺序输出的顺序在空BST中插入节点来创建BST的。它是？我的意思是，在从预序遍历输出构造唯一BST的情况下，有与上述步骤等价的步骤吗。或者我们只需要按照BST创建算法，按照级别顺序遍历输出的顺序在空BST中插入节点？

Answer 1

或者我们只需要按照BST创建算法，按照级别顺序遍历输出的顺序在空BST中插入节点？

这可以更有效地完成（线性时间vs.Θ（n log（n）），但需要小心完成。在您的口头描述中，何时移动到父级中的新节点的问题需要更加精确。

假设在构建树时，对于每个节点v，存储一个辅助变量c（v），这是一个截止值，超过这个值，一个项就不能是v的子项。

>

当你开始时，你用c构造节点5（5) = ∞ (因为只有当某个东西大于∞时，它才不会是这个节点的子节点）。

下一项是1。自从4

下一项是8。又是8个

类似地，1成为4的子级，并将其截止级别设为4。

7不能是4岁的孩子。它大于4的截止水平。我们继续上一级的下一个节点，即8。它确实可以是一个8岁的孩子，然后变成它的左孩子，把8作为它自己的临界值。

继续如上所述：

>

每个节点都可以是上一级节点的子节点，如果它在上一级节点的截止值之下。如果没有，则移动到上一级中的下一个节点作为候选。

对于上一级别中新节点小于截止值的第一个节点：

>

如果小于节点，则变为左子节点，并将父节点的值作为其截止值。

如果它大于节点，它将成为右子节点，并将父节点的截止值作为自己的截止值。