LeetCode刷题【1382】将二叉搜索树变平衡

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

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

题解

最直观的思路解法，因为本身给出的是一个二叉搜索树，但是不平衡，所以可以直接进行中序遍历，拿到一个递增的list，再用这个list直接构建一个新的平衡二叉树就可以了

import java.util.ArrayList;

/**
 * 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 {
    private List<Integer> list = new ArrayList<>();
    public TreeNode balanceBST(TreeNode root) {
        //先取到中序遍历结果，
        dsf(root);

        return createBST(0,list.size()-1);
    }

    private void dsf(TreeNode root){
        if(root.left!=null)dsf(root.left);
        list.add(root.val);
        if(root.right!=null)dsf(root.right);
    }

    private TreeNode createBST(int left, int right){
        if (right < left) return null;
        int mid = (left + right)>>1;
        TreeNode node = new TreeNode(list.get(mid));
        node.left = createBST(left,mid-1);
        node.right = createBST(mid+1,right);
        return node;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

根据特性，数组的中间一位为root节点，左边为左子树上的中序遍历结果，右边为右子树上的中序遍历结果，所以可以直接取中间一位作为根节点，左边的集合和右边的集合分别递归构建即可。