参考： 有人问我这个问题@MS SDE采访时，第3轮。而且这不是一个家庭作业的问题。我也给它一个思想和提我下面的方法。

Reference: I was asked this question @MS SDE interview, 3rd round. And it's not a homework problem. I also gave it a thought and mentioning my approach below.

问： 修改的BST，使之成为尽可能均衡。不用说，你应该这样做尽可能高效。

Question: Modify a BST so that it becomes as balanced as possible. Needless to mention, you should do it as efficient as possible.

提示： 记者说，这是一个合乎逻辑的问题，如果你有不同的想法，你会得到答案。没有复杂的编码参与。 - >说了这么多，我不认为他是希望我指向AVL / RB树

Hint: Interviewer said that this is a logical question, if you think differently you will get the answer. No difficult coding involved. --> Having said that, I do not think he was expecting me to point to AVL/RB Trees.

我的解决方法： 我建议，我会做序树的遍历，取中间的元素作为新的树根（让称之为新根）。然后去中间元素的左侧部分，取其中间元素作为树的根新根左子树的根。对于右侧同样做。 这样做递归将给最佳平衡BST。

My Solution: I proposed that, I would do inorder traversal of tree, take middle element as root of new tree(lets call it new root). Then go to the left part of middle element, take its middle element as root of left subtree of tree rooted new root. Similarly do for right part. Doing this recursively will give the optimal balanced BST.

为什么我在这里张贴： 但他并不满足于答案:(那么，有没有真的这样做W / O去为权重/ RB着色战略，还是他只是鬼混我的方法吗？ 请把你的想法专家

Why I am posting it here: But he was not satisfied with the answer :( So, is there really a way of doing this w/o going for weights/RB coloring strategy, or was he just fooling around with me? Please put in your expert thoughts.

复制？不！的 我知道有这个问题但提出请求的解决方案过于复杂，和其他人谈论AVL树。

Duplicate? No! I know there is this question but the solution proposed by requester is too complicated, and other one talks about AVL trees.

感谢很多提前！

推荐答案

您可能要考虑在 Day-Stout-Warren算法，这是一个为O​​（n） - 时间，O（1）空间算法重塑一个任意的二叉搜索树成一个完整的二叉树。直观地说，该算法的工作方式如下：

You might want to look into the Day-Stout-Warren algorithm, which is an O(n)-time, O(1)-space algorithm for reshaping an arbitrary binary search tree into a complete binary tree. Intuitively, the algorithm works as follows:

该算法的优点在于它以线性时间运行，只需要不断的内存开销;事实上，它只是重塑底层的树，而不是创建一个新的树和复制了旧数据。这也是相对简单的code了。

The beauty of this algorithm is that it runs in linear time and requires only constant memory overhead; in fact, it just reshapes the underlying tree, rather than creating a new tree and copying over the old data. It is also relatively simple to code up.

希望这有助于！