题目描述：
给你一棵二叉搜索树，请你返回一棵 平衡后 的二叉搜索树，新生成的树应该与原来的树有着相同的节点值。
如果一棵二叉搜索树中，每个节点的两棵子树高度差不超过 1 ，我们就称这棵二叉搜索树是 平衡的 。
如果有多种构造方法，请你返回任意一种。
示例：
输入：root = [1,null,2,null,3,null,4,null,null]
输出：[2,1,3,null,null,null,4]
解释：这不是唯一的正确答案，[3,1,4,null,2,null,null] 也是一个可行的构造方案。
提示：
树节点的数目在 1 到 10^4 之间。
树节点的值互不相同，且在 1 到 10^5 之间。
投机取巧的一种方法是先中序遍历，然后重新构造二叉树
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode(int x) { val = x; }* }*/
class Solution {
public TreeNode balanceBST(TreeNode root){
List<Integer> sortList = new ArrayList<>();// 中序遍历构造有序链表inOrder(root,sortList);// 有序链表构造平衡二叉树return buildTree(sortList,0,sortList.size()-1);}private void inOrder(TreeNode node,List<Integer> sortList){
if (node != null){
inOrder(node.left,sortList);sortList.add(node.val);inOrder(node.right,sortList);}}//有序链表构造平衡二叉树private TreeNode buildTree(List<Integer> sortList, int start, int end) {
if (start > end){
return null;}// 中间节点为rootint mid = start + (end - start >> 1);TreeNode root = new TreeNode(sortList.get(mid));// 递归构造左右子树root.left = buildTree(sortList,start,mid-1);root.right = buildTree(sortList,mid+1,end);// 返回rootreturn root;}
}