参考： 这是我在微软SDE面试的第三轮被问到的问题，而且这不是一道作业问题。我思考了一下，下面提供了我的方法。
问题： 修改一个二叉搜索树，使其尽可能平衡。毋庸置疑，您应该尽可能高效地完成它。
提示：
面试官说这是一个逻辑问题，如果您有不同的想法，就会得到答案。没有涉及复杂的编码。
--> 话虽如此，我认为他并不希望我指向AVL/RB树。
我的解决方法： 我提出，我会对树进行中序遍历，将中间元素作为新树（称为新根）的根。然后进入中间元素的左部分，将其中间元素作为新根左子树的根。右部分也是如此。 递归地执行此操作将得到最优平衡的BST。
为什么我在这里发布它： 但他对答案不满意:(那么，是否真的有办法在不使用重量/ RB着色策略的情况下完成此操作，还是他只是在戏弄我？ 请发表您的专业见解。
重复？没有！ 我知道有这个问题，但请求者提出的解决方案太复杂了，而另一个则谈到了AVL树。
"尽可能平衡" = 完全二叉树1。没有比它更平衡的了。
解决方案很简单 - 构建一个“空”的完全二叉树，并同时对新树和输入树进行中序遍历，以填充完整树。
完成后，您将拥有最平衡的树，并且这种方法的时间复杂度为O(n)。
编辑：
应按以下步骤执行：
n个节点的虚拟完全树。每个节点的所有值都将初始化为某些垃圾值。originalIter，(2)用于新树的newIter（使用垃圾值初始化）。两个迭代器都将按中序遍历返回元素。执行以下操作以使用原始值填充树：
while (originalIter.hasNext()):
newIter.next().value = originalIter.next().value
(1) (来自维基百科): 完全二叉树是一种二叉树，其中除了最后一层可能不完全填充外，每个层都是完全填充的，并且所有节点尽可能靠左。
DSW算法可以在O(n)时间内解决这个问题。该算法的步骤如下：
1] Using right-rotation operations, turn the tree into a linked list
(a.k.a. backbone or vine)
2] Rotate every second node of the backbone about its parent to turn
the backbone into a perfectly balanced BST.
import java.util.Vector;
public class ConvertBSTIntoBalanced {
public static void main(String[] args) {
TreeNode node1 = new TreeNode(1);
TreeNode node2 = new TreeNode(2);
TreeNode node3 = new TreeNode(3);
TreeNode node4 = new TreeNode(4);
node1.right = node2;
node2.right = node3;
node3.right = node4;
ConvertBSTIntoBalanced convertBSTIntoBalanced = new ConvertBSTIntoBalanced();
TreeNode balancedBSTRoot = convertBSTIntoBalanced.balanceBST(node1);
}
private void saveNodes(TreeNode node, Vector<TreeNode> nodes) {
if (node == null)
return;
saveNodes(node.left, nodes);
nodes.add(node);
saveNodes(node.right, nodes);
}
private TreeNode buildTree(Vector<TreeNode> nodes, int start, int end) {
if (start > end)
return null;
int mid = (start + end) / 2;
TreeNode midNode = nodes.get(mid);
midNode.left = buildTree(nodes, start, mid - 1);
midNode.right = buildTree(nodes, mid + 1, end);
return midNode;
}
public TreeNode balanceBST(TreeNode root) {
Vector<TreeNode> nodes = new Vector<>();
saveNodes(root, nodes);
return buildTree(nodes, 0, nodes.size() - 1);
}
public class TreeNode {
public Integer val;
public TreeNode left;
public TreeNode right;
public TreeNode(Integer x) {
val = x;
}
}
}
public void deleteNode(Node node, int value) {
Node z = null;
Node x, y;
while (node != null){
if (node.data == value) {
z = node;
}
if (node.data <= value) {
node = node.right;
} else {
node = node.left;
}
}
if (z == null) {
System.out.println("Couldn't find key in the tree");
return;
}
y = z;
int yOriginalColor = y.color;
if (z.left == null) {
x = z.right;
rbTransplant(z, z.right);
} else if (z.right == null) {
x = z.left;
rbTransplant(z, z.left);
} else {
y = minimum(z.right);
yOriginalColor = y.color;
x = y.right;
if (y.parent == z) {
x.parent = y;
} else {
rbTransplant(y, y.right);
y.right = z.right;
y.right.parent = y;
}
rbTransplant(z, y);
y.left = z.left;
y.left.parent = y;
y.color = z.color;
}
if (yOriginalColor == 0){
fixDelete(x);
}
}