是否有可能建立从最大堆二叉搜索树在O（n）的步骤是什么？

Question

我认为这是不可能的，因为如果它实际上是，人们将建立最大堆，然后用它来构建BST，我认为不是这样的。

请给一个证明一个答案。

Answer 1

你不能。

堆，它可以包含超过一半的节点，所述的底部水平可以是在堆完全无序的。 （想象所有的内部节点是少于所有的叶节点）。

构建BST将决定这些节点的顺序，但排序需要O（N log n）的时间，所以你不能建立在O（n）的时间BST。