_1382.java

packagecom.fishercoder.solutions.secondthousand;

importcom.fishercoder.common.classes.TreeNode;
importjava.util.ArrayList;
importjava.util.List;

publicclass_1382 {
publicstaticclassSolution1 {
publicTreeNodebalanceBST(TreeNoderoot) {
List<Integer> inorder = inorder(root, newArrayList<>());
returndfs(inorder, 0, inorder.size() - 1);
 }

privateList<Integer> inorder(TreeNoderoot, List<Integer> list) {
if (root == null) {
returnlist;
 }
inorder(root.left, list);
list.add(root.val);
returninorder(root.right, list);
 }

privateTreeNodedfs(List<Integer> nums, intstart, intend) {
if (end < start) {
returnnull;
 }
intmid = (start + end) / 2;
TreeNoderoot = newTreeNode(nums.get(mid));
root.left = dfs(nums, start, mid - 1);
root.right = dfs(nums, mid + 1, end);
returnroot;
 }
 }
}