1

可能重复：
将最大堆转换为二叉搜索树

在不使用额外空间的情况下，尽可能高效地将最小堆转换为二叉搜索树。（允许递归）。

这个问题一直让我发疯。必须有一种方法可以使用 min-heap 属性来比蛮力更有效地执行此操作。例如，给定这个最小堆：

    [1, 7, 6, 9, 8, 21, 15] =

                1
             /     \  
           7        6
          / \      / \
         9   8   21   15

我们立即知道，根据定义，根将是我们二叉搜索树中最左边的节点。我们还知道，最小堆中任何节点的右子节点都不会违反 BST 属性（parent.right > parent）。

我们如何利用这些事实有效地就地创建 BST？

4

0 回答 0