给你一棵二叉搜索树，请你返回一棵 平衡后 的二叉搜索树，新生成的树应该与原来的树有着相同的节点值。如果有多种构造方法，请你返回任意一种。

    如果一棵二叉搜索树中，每个节点的两棵子树高度差不超过 1 ，我们就称这棵二叉搜索树是 平衡的 。

    示例 1：
    image.png

    输入：root = [1,null,2,null,3,null,4,null,null]
    输出：[2,1,3,null,null,null,4]
    解释：这不是唯一的正确答案，[3,1,4,null,2,null,null] 也是一个可行的构造方案。
    示例 2：

    输入: root = [2,1,3]
    输出: [2,1,3]

    提示：

    树节点的数目在 [1, 104] 范围内。
    1 <= Node.val <= 105

    1. /**
    2.  * Definition for a binary tree node.
    3.  * public class TreeNode {
    4.  *     int val;
    5.  *     TreeNode left;
    6.  *     TreeNode right;
    7.  *     TreeNode() {}
    8.  *     TreeNode(int val) { this.val = val; }
    9.  *     TreeNode(int val, TreeNode left, TreeNode right) {
    10.  *         this.val = val;
    11.  *         this.left = left;
    12.  *         this.right = right;
    13.  *     }
    14.  * }
    15.  */
    16. class Solution {
    17.     List<Integer> list = new ArrayList<>();
    18.     public TreeNode balanceBST(TreeNode root) {
    19.         get(root);
    20.         return dfs(0, list.size() - 1);
    21.     }
    23.     void get(TreeNode root) {
    24.         if (root == null) return;
    25.         get(root.left);
    26.         list.add(root.val);
    27.         get(root.right);
    28.     }
    30.     TreeNode dfs(int l, int r) {
    31.         if (l > r) return null;
    32.         int mid = l + r >> 1;
    33.         TreeNode root = new TreeNode(list.get(mid));
    34.         root.left = dfs(l, mid - 1);
    35.         root.right = dfs(mid + 1, r);
    36.         return root;
    37.     }
    38. }