1382. 将二叉搜索树变平衡 (opens new window)

1.中序遍历

分析：用数组保存二叉搜索树的中序遍历结果，此时数组一定是递增的。然后从数组的中间部分分裂，分别构造二叉树。

原地手撕AVL难度过大...

class Solution {
    List<Integer> list=new ArrayList<>();
    public TreeNode balanceBST(TreeNode root) {
        dfs(root);
        int[] nums=list.stream().mapToInt(Integer::valueOf).toArray();
        return build(nums,0,nums.length-1);
    }
    public void dfs(TreeNode root){
        if(root.left!=null) dfs(root.left);
        list.add(root.val);
        if(root.right!=null) dfs(root.right);
    }
    public TreeNode build(int[] nums,int start,int end){
        int mid=(start+end)>>1;
        TreeNode root=new TreeNode(nums[mid]);
        root.left=start<=mid-1?build(nums,start,mid-1):null;
        root.right=mid+1<=end?build(nums,mid+1,end):null;
        return root;
    }
}