参考： 我被问到这个问题@MS SDE 面试，第三轮。这不是家庭作业的问题。我也考虑过并在下面提到我的方法。
问题： 修改 BST，使其尽可能平衡。不用说，你应该尽可能高效地完成它。
提示：
面试官说这是一个逻辑问题，如果你有不同的想法就会得到答案。不涉及困难的编码。
--> 话虽如此，我认为他并不希望我指向 AVL/RB 树。
我的解决方案： 我建议，我对树进行中序遍历，将中间元素作为新树的根（我们称之为新根）。然后转到中间元素的左侧部分，将其中间元素作为以树为根的新根的左子树的根。对右侧部分进行同样的操作。 递归地执行此操作将给出最佳平衡 BST。
为什么我在这里发布它： 但他对答案并不满意:( 那么，是否真的有一种方法可以做到这一点而不需要权重/RB 着色策略，或者他只是在跟我开玩笑？ 请提出您的专业想法。
重复？不！ 我知道有这个问题，但是请求者提出的解决方案太复杂了，另外一个讲的是AVL树。
您可能想研究一下 Day-Stout-Warren 算法，这是一种 O(n) 时间、O(1) 空间算法，用于将任意二叉搜索树重塑为完整二叉树。直观上，该算法的工作原理如下：
该算法的优点在于它以线性时间运行并且仅需要恒定的内存开销；事实上，它只是重塑底层树，而不是创建新树并复制旧数据。编码起来也比较简单。
希望这有帮助！
“尽可能平衡”=完整（或完整）二叉树1。你无法比它更平衡了。
解决方案很简单 - 构建一个“空”完整二叉树，并以中序遍历方式（同时）迭代新树和输入树以填充完整树。
完成后，您就拥有了可以获得的最平衡的树，这种方法的时间复杂度是
O(n)编辑：
应按照以下步骤完成此操作：
noriginalIternewIter执行以下操作，用原始值填充树：
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.
这会将您的正常 BST 转换为平衡 BST，其最小可能高度为 O(n)。首先，将所有节点保存到一个向量中。然后，根为 mid 元素，递归地从 0 到 mid-1 构建一棵树作为其左子节点，并从 mid+1 到 vector.size()-1 构建一棵树作为其右子节点。在完成所有这些步骤之后，root 保持平衡的 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;
}
}
}
我希望它有帮助。
这是一个带有删除功能的BST：
/** This class is a part of {@code package tree}. Do not change the package structure.
* Make sure that your IDE do not change it to for example {@code package src.tree}.
* If it happens, please revert it once you finish the implementation.
*/
package tree;
/**
* Binary search tree with integer keys (values). {@code insert} method is
* provided.
*
* @author dongwoo
*
*/
public class BST {
Node root;
/**
* Q2 - Task1 TODO: Implement "find" method. The method should return "true" if
* a tree contains the node with value, otherwise return "false". You can define
* additional functions in class BST or Node if you need.
*
* @param value
* @return return true if the tree contains the node with value otherwise false
*/
public Boolean find(int value) {
// start your code
Node current = root;
while(current!=null){
if(current.value>value){
current=current.left;
}else if(current.value<value){
current=current.right;
}else{
return true;
}
}
return false;
// end your code
}
/**
* Q2 - Task2 TODO: Implement "delete" method. Find the node with {@code value}
* and remove it from the tree. If the target node has two children, use
* successor to replace the target node. You can define additional functions in
* class BST or Node if you need.
*
* Do not care about the case where the target node does not exist.
*
* @param value value of the target node
*/
public void delete(int value) {
Node current = root;
Node parent = null;
// Find the node to be deleted
while (current != null && current.value != value) {
parent = current;
if (value < current.value) {
current = current.left;
} else {
current = current.right;
}
}
if (current == null) {
return; // Value not found in the tree
}
// Node with two children
if (current.left != null && current.right != null) {
Node successor = current.right;
Node successorParent = current;
while (successor.left != null) {
successorParent = successor;
successor = successor.left;
}
current.value = successor.value;
current = successor;
parent = successorParent;
}
// Node with only one child or no child
Node child = (current.left != null) ? current.left : current.right;
if (current != root) {
if (current == parent.left) {
parent.left = child;
} else {
parent.right = child;
}
} else {
root = child; // If root is to be deleted
}
if (child != null) {
child.parent = parent;
}
}
/**
* Q2 - Task3 TODO: Implement "sumEvenNodes" function. The method should return
* print the sum of the nodes that have an even number of direct children (zero
* is an even number). You can define additional functions in class BST or Node
* if you need.
*
* @return Sum of the nodes that have an even number of direct children
*/
public int sumEvenNodes() {
//start your code
return sumEvenNodesHelper(root);
//end your code
}
private int sumEvenNodesHelper(Node node) {
if (node == null) {
return 0;
}
int sum = 0;
int childrenCount = 0;
if (node.left != null) {
childrenCount++;
}
if (node.right != null) {
childrenCount++;
}
if (childrenCount % 2 == 0) {
sum += node.value;
}
sum += sumEvenNodesHelper(node.left);
sum += sumEvenNodesHelper(node.right);
return sum;
}
public class Node {
public Integer value;
public Node parent;
public Node left;
public Node right;
public Node(Integer value) {
this.value = value;
this.parent = null;
this.left = null;
this.right = null;
}
}
public BST() {
root = null;
}
/**
* Insert a new node based on an input value. Do not modify the method.
*
* Do not consider the case where a tree already has the node with the same
* value.
*
* @param value value of inserted node
* @return inserted node (not the entire tree)
*/
public Node insert(int value) {
Node parent = null;
Node current = root;
while (current != null) {
if (current.value < value) {
parent = current;
current = current.right;
} else if (current.value > value) {
parent = current;
current = current.left;
}
}
if (parent == null && current == null) {
root = new Node(value); // no parent = root is empty
return root;
} else {
Node newNode = new Node(value);
if (parent.value < value) {
parent.right = newNode;
newNode.parent = parent;
} else if (parent.value > value) {
parent.left = newNode;
newNode.parent = parent;
}
return newNode;
}
}
}