LeetCode 1382. 将二叉搜索树变平衡

约 5 分钟
文章信息 6 个分类 6 个标签
分类
LeetCode CodeTop 中等 未解决 1-2 拼多多
标签
深度优先搜索 树 二叉树 贪心 二叉搜索树 分治

题目描述

✅ 1382. 将二叉搜索树变平衡

image-20260929082527065

image-20260929082527198

题意分析

输入是一棵二叉搜索树，需要返回一棵包含相同节点值的平衡二叉搜索树。平衡要求每一个节点的左右子树高度差都不超过一，而不只是根节点看起来两边差不多。

可以改变树的形状，满足条件的结果不唯一。下面的实现先读取原树的全部值，再创建新树；原树节点的左右连接不会被修改。

解法：中序 + 递归构建

核心思路

[!blue]

二叉搜索树的中序遍历天然按数值有序，因此先用中序把值收集到数组，就把树的形状问题与数值顺序分开了。无需再排序，也不能用前序或层序结果直接代替有序数组。

对有序数组的闭区间 [left, right]，选择中间位置作为根。它左边的值都属于左子树，右边的值都属于右子树，左右分别用同样方法递归构建，因此每一层都保持二叉搜索树的大小关系。

中点把剩余节点分成大小至多相差一的两段，并且每个子区间都继续近似对半划分。这种构造不会把节点集中到某一条长链上，各层子问题规模同步缩小，最终每个节点的左右子树高度至多相差一。

中点从两个子区间中排除，保证每个值恰好用于创建一个节点。只有 left > right 才是空区间；两端相等时还有一个值，应创建叶子，再由它的两个空区间返回空孩子。

原树可能已经退化为很深的链，所以收集中序值使用显式栈；重建阶段的区间持续对半，递归深度仅为对数级。遍历栈与建树递归承担不同工作，不能把原树的深度直接当成重建深度。

解题步骤

  1. 用显式栈中序遍历原树，按访问顺序保存所有节点值。
  2. 对整个有序值数组调用构造函数。
  3. 空区间返回空；否则以中点值创建当前根。
  4. 用中点左侧区间构造左子树，右侧区间构造右子树，两边都排除中点。
  5. 返回新根节点。

代码实现

class Solution {
    public TreeNode balanceBST(TreeNode root) {
        List<Integer> values = new ArrayList<>();
        Deque<TreeNode> stack = new ArrayDeque<>();
        TreeNode node = root;

        while (node != null || !stack.isEmpty()) {
            // 先沿左链入栈，弹出顺序就是中序访问顺序。
            while (node != null) {
                stack.push(node);
                node = node.left;
            }

            node = stack.pop();
            // 访问当前值后，再转向它的右子树。
            values.add(node.val);
            node = node.right;
        }

        return build(values, 0, values.size() - 1);
    }

    private TreeNode build(List<Integer> values, int left, int right) {
        // 闭区间只有左端超过右端才为空，单点仍需建叶子。
        if (left > right) {
            return null;
        }

        // 中点作根，左右子区间均排除中点并递归平分。
        int mid = left + (right - left) / 2;
        TreeNode node = new TreeNode(values.get(mid));

        node.left = build(values, left, mid - 1);
        node.right = build(values, mid + 1, right);

        return node;
    }
}

func balanceBST(root *TreeNode) *TreeNode {
    values := make([]int, 0)
    stack := make([]*TreeNode, 0)
    for root != nil || len(stack) > 0 {
        // 先沿左链入栈，弹出顺序就是中序访问顺序。
        for root != nil {
            stack = append(stack, root)
            root = root.Left
        }
        root = stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        // 访问当前值后，再转向它的右子树。
        values = append(values, root.Val)
        root = root.Right
    }

    var build func(int, int) *TreeNode
    build = func(left, right int) *TreeNode {
        // 闭区间只有左端超过右端才为空，单点仍需建叶子。
        if left > right {
            return nil
        }
        // 中点作根，左右子区间均排除中点并递归平分。
        mid := left + (right-left)/2
        node := &TreeNode{Val: values[mid]}
        node.Left = build(left, mid-1)
        node.Right = build(mid+1, right)
        return node
    }

    return build(0, len(values)-1)
}

复杂度分析

设节点数为 $n$。

  • 时间复杂度：$O(n)$，中序读取和重建各处理每个值一次。
  • 辅助空间复杂度：$O(n)$，用于有序值数组和原树遍历栈；重建递归栈为 $O(\log(n+1))$。返回的新树另占 $O(n)$。

关键点总结

[!green]

  • 原 BST 的中序结果已经有序，直接用于构建即可。
  • 中点保证左右规模近似相等，递归继续平分使每个节点都满足高度平衡。
  • 原树深度决定遍历栈上界，新树按区间对半构建决定递归深度。

易错点总结

[!yellow]

  • 使用无序的前序或层序结果重建，会破坏二叉搜索树的数值关系。
  • left == right 不是空区间，直接返回空会漏掉叶子。
  • 左右子区间不能包含中点，否则会重复创建节点或无法缩小递归规模。
  • 总是选择区间端点作为根，会再次构造成链，无法达到平衡。
  • 只平衡根节点不够，所有子区间都必须按相同规则递归构建。

相似题目

题目 难度 关联与区别
108. 将有序数组转换为二叉搜索树 简单 先中序收集有序节点，再按中点分治构造平衡BST，复用有序数组建树的结构。
98. 验证二叉搜索树 中等 重建后仍要保持中序严格有序，改变的是高度和连接而不是数值集合。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2025/63975794
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！