思路分析：

此题目的是想将二叉搜索树变成一棵平衡二叉搜索树，【平衡】要求它的左右两个子树的高度差的绝对值不超过 1。构建的过程最直观的想法就是左右子树的大小越平均，这棵树或许会更平衡。所以通过中序遍历将原来的二叉搜索树转换为一个有序集合，然后对这个有序集合进行递归建树。

有序集合的左右区间分别为 left 和 right，以索引表示，即从 0 开始，记为 [left，right]，构建过程如下：

• 取 mid = left + (right – left) / 2，即中心位置作为树的当前节点的值；
• 如果 left <= mid – 1；那么递归地将区间 [left，mid – 1] 作为当前节点的左子树；
• 如果 right >= mid + 1；那么递归地将区间 [mid + 1，right] 作为当前节点的右子树。

完整代码：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    List<Integer> nodeList = new ArrayList<>();

    public TreeNode balanceBST(TreeNode root) {
        traversal(root, nodeList);
        return listToTree(0, nodeList.size() - 1);
    }

    public void traversal(TreeNode curr, List<Integer> nodeList) {
        if (curr == null) {
            return;
        }
        traversal(curr.left, nodeList);
        nodeList.add(curr.val);
        traversal(curr.right, nodeList);
    }

    // List 转 TreeNode
    public TreeNode listToTree(int left, int right) {
        // 找到中心位置
        int mid = left + (right - left) / 2;
        TreeNode curr = new TreeNode(nodeList.get(mid));
        if (left <= mid - 1) {
            curr.left = listToTree(left, mid - 1);
        }
        if (right >= mid + 1) {
            curr.right = listToTree(mid + 1, right);
        }
        return curr;
    }

}

由中序遍历获取有序集合时间复杂度为 O(n)，构建树的时候时间复杂度也为 O(n)，总的时间复杂度为 O(n)。