algorithm - 从层序遍历输出构造一个唯一的二叉搜索树

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，所以我将其作为左 child pf 5。8 大于 5，因此我将其作为 5 的右 child 。(它不能是 4 的 child ，因为在那种情况下它应该小于 5。因此它不能出现在第 2 级)。然后是 1 和 7。1 应该是 4 的左 child ，因为它小于 4。7 不能是 4 的右 child ，因为它也大于 5。所以它应该在 5 的右子树上。因此它必须是 8 的左子树，因为 7 < 8。我们可以对所有子树继续相同。

我的感觉是，这竟然是正常的BST创建。也就是说，它是通过在层序输出序列中的空 BST 中插入节点来创建 BST。是吗？我的意思是，在从预序遍历输出构造唯一 BST 的情况下，是否有与上述步骤相同的步骤。还是只需要按照BST创建算法，在层序遍历输出的序列中，在空BST中插入节点？

Answer 1

Or we just have to follow BST creation algorithm and insert nodes in empty BST in the sequence of level order traversal output?

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

假设在构建树时，对于每个节点 v，您存储一个辅助变量 c(v)，它是项目无法超过的截止值成为 v 的 child 。

• 开始时，您构造节点 5 且 c(5) = ∞(因为仅当某物大于 ∞ 会不会是这个节点的子节点)。

• 下一项是 1。因为 4 < c(5) = ∞，所以 1 可以是 5 的 child ；因为它更小，所以它一定是左 child 。由于它是左 child ，它的截止值是父代的值，所以c(4) = 5。

• 下一项是 8。同样，8 < c(5) = ∞，所以它可以是一个 child ，但它必须是正确的 child 。由于它是右 child ，它的截止值是其父级的截止值，所以c(8) = ∞。

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

• 7 不能是 4 的 child 。它大于 4 的截止级别。我们继续前进到上一级的下一个节点，即 8。它确实可以是 8 的 child ，并且成为它的左 child ，以 8 作为自己的截止水平。

继续如上:

• 每个节点都可以是上一层节点的子节点，前提是它低于上一层节点的截止点。如果不是，则作为候选继续上一层的下一个节点。

• 对于新节点小于截止值的前一级别中的第一个节点:

  • 如果小于该节点，则成为左 child ，并取父节点的值作为其截止值。

  • 如果大于该节点，则成为右 child ，并以父节点的截断作为自己的截断。