题目描述

给你一棵二叉搜索树，请你返回一棵平衡后的二叉搜索树，新生成的树应该与原来的树有着相同的节点值。

如果一棵二叉搜索树中，每个节点的两棵子树高度差不超过 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 之间。

算法分析

• 1、对本来的二叉搜索树通过中序遍历变成一个有序的数组
• 2、对于一个有序的数组构建一棵平衡二叉树的方法，最中间的元素当做根，左边的元素当做左子树，右边的元素当做右子树

时间复杂度$O(n)$

Java 代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    static int N = 10010;
    static int[] val = new int[N];
    static int tt;
    static void dfs(TreeNode root)
    {
        if(root == null) return;
        dfs(root.left);
        val[++ tt] = root.val;
        dfs(root.right);
    }
    static TreeNode build(int left,int right)
    {
        if(left > right) return null;
        int mid = left + right >> 1;
        TreeNode root = new TreeNode(val[mid]);
        root.left = build(left,mid - 1);
        root.right = build(mid + 1,right);
        return root;
    }
    public TreeNode balanceBST(TreeNode root) {
        tt = 0;
        dfs(root);
        return build(1,tt);
    }
}