标签： 平衡二叉树

目标

给你一棵二叉搜索树，请你返回一棵 平衡后 的二叉搜索树，新生成的树应该与原来的树有着相同的节点值。如果有多种构造方法，请你返回任意一种。

如果一棵二叉搜索树中，每个节点的两棵子树高度差不超过 1 ，我们就称这棵二叉搜索树是 平衡的 。

示例 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] 也是一个可行的构造方案。

示例 2：

输入: root = [2,1,3]
输出: [2,1,3]

说明：

• 树节点的数目在 [1, 10^4] 范围内。
• 1 <= Node.val <= 10^5

思路

将给定的二叉搜索树变平衡。

中序遍历二叉搜索树，结果列表有序，从中间重新构建 BST。

代码

/**
 * @date 2026-02-09 8:56
 */
public class BalanceBST1382 {

    public TreeNode balanceBST(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        dfs(list, root);
        int l = 0, r = list.size() - 1;
        return buildTree(list, l, r);
    }

    public void dfs(List<Integer> nums, TreeNode node) {
        if (node == null) {
            return;
        }
        dfs(nums, node.left);
        nums.add(node.val);
        dfs(nums, node.right);
    }

    public TreeNode buildTree(List<Integer> nums, int l, int r) {
        if (l == r) {
            return new TreeNode(nums.get(l));
        } else if (l > r) {
            return null;
        }
        int m = l + (r - l) / 2;
        return new TreeNode(nums.get(m), buildTree(nums, l, m - 1), buildTree(nums, m + 1, r));
    }

}

/**
 * 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;
 * }
 * }
 */

性能