1382. 将二叉搜索树变平衡（java）

解题思路

首先应当构建二叉树中序遍历数组，二叉树的中序遍历是升序的有序数组，每次通过选取二叉树中序遍历数组的中间位置元素为根结点，这样二叉树的左右子树高度差不会超过1，左右子树的元素分别位于根结点的左右两边，然后递归构建二叉平衡树即可。

代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
 import java.util.*;
class Solution {
    List<Integer> list = new ArrayList<Integer>();
    public TreeNode balanceBST(TreeNode root) {
        getTree(root);
       return helper(0,list.size()-1);
    }
    public void getTree(TreeNode root){//中序遍历的结果为升序 
        if(root.left!=null) getTree(root.left); //获取左子树    
        list.add(root.val);//获取根结点
        if(root.right!=null) getTree(root.right);//获取右子树
    }
    public TreeNode helper(int left,int right){
        if(left>right)return null;
        int mid=(left+right)/2;//以中间位置元素建立二叉树
        TreeNode root=new TreeNode(list.get(mid));
        root.left=helper(left,mid-1);
        root.right=helper(mid+1,right);
        return root;
    }
}

1382. 将二叉搜索树变平衡（java）

原文：https://www.cnblogs.com/zhimeng-yabiao/p/14609249.html