给你一棵二叉搜索树,请你返回一棵 平衡后 的二叉搜索树,新生成的树应该与原来的树有着相同的节点值。如果有多种构造方法,请你返回任意一种。
如果一棵二叉搜索树中,每个节点的两棵子树高度差不超过 1 ,我们就称这棵二叉搜索树是 平衡的 。
题解
class Solution {
List orderList = new ArrayList<>();
public TreeNode balanceBST(TreeNode root) {
getOrderList(root);
return buildBalanceBST(0, orderList.size() - 1);
}
public void getOrderList(TreeNode node) {
if(node == null) {
return;
}
getOrderList(node.left);
orderList.add(node.val);
getOrderList(node.right);
}
public TreeNode buildBalanceBST(int l, int r) {
int mid = (l + r) >> 1;
TreeNode root = new TreeNode(orderList.get(mid));
if(l <= mid - 1) {
root.left = buildBalanceBST(l, mid - 1);
}
if(r >= mid + 1) {
root.right = buildBalanceBST(mid + 1, r);
}
return root;
}
}



