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

2025-04-16 HGNULB 约 7 分钟

文章信息 6 个分类 6 个标签

分类

题目描述

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

题意分析

给定一棵二叉搜索树的根节点，要返回一棵平衡的二叉搜索树，且它包含的节点值集合与原树完全相同。这里的「平衡」按题目定义是：每个节点的左右子树高度差不超过 1。如果有多种答案，返回任意一棵即可。

「返回任意一棵」这句话极大地放宽了要求——不需要模拟 AVL 的旋转、不需要保持任何与原树结构相关的性质，只要值集合相同且结果是一棵平衡的 BST 就行。这把一道看似要写平衡树的题变成了一道构造题。

两个约束要分开看。BST 的约束是「中序遍历结果严格递增」；平衡的约束是「高度差不超过 1」。前者只管值的相对顺序，后者只管形状。关键的观察是：这两个约束几乎是正交的——值的顺序由中序序列决定，形状可以自由挑选，只要挑的形状仍然让中序序列保持递增即可。

输入本身已经是 BST 这一点必须用上：它意味着中序遍历天然给出一个有序数组，不需要额外排序。若忽略这个前提去做排序，会白白多出 $O(n \log n)$。

约束里节点数在 1 到 $10^4$ 之间，节点值互不相同且在 1 到 $10^5$ 之间。规模不大，但原树可能已经退化成一条长链（比如插入的是递增序列），所以中序遍历的递归深度最坏可达 $10^4$。

边界要留意三点：树至少有一个节点，不会传入空根；节点值互不相同，不需要考虑重复值的排列；返回的必须是新构造的树或重新链接过的原节点，不能原样返回入参。

解法：中序 + 递归构建

核心思路

题目只要求节点值相同，不要求保留原来的形状，因此无需实现旋转。利用 BST 的中序遍历有序，可以分成两个阶段：

中序遍历原树，得到严格递增数组 values。

对数组区间反复取中点作为根，递归构造左右子树。

定义 build(left, right)：用 values[left..right] 构造一棵平衡 BST，并保证其中序序列仍是这一段。取 mid = left + (right - left) / 2，左子树使用 [left, mid-1]，右子树使用 [mid+1, right]。

正确性包含两部分。第一，中点左侧的值都小于根、右侧都大于根；递归子树也保持同一性质，所以构造结果是 BST，且每个数组元素恰好被选一次，节点值不重不漏。第二，每次划分后左右区间的长度至多相差 1；递归构造出的两棵子树高度至多相差 1，因此每个节点都满足 $\lvert h_L-h_R\rvert\le 1$。

原树可能退化成一条含 $10^4$ 个节点的链。为避免中序递归栈过深，代码使用显式栈迭代遍历；新树高度为 $O(\log n)$，构造阶段递归是安全且清晰的。

解题步骤

维护当前节点和显式栈：不断向左入栈，弹出后记录值，再转向右子树，得到有序数组。

调用 build(0, values.size()-1)；空区间 left > right 返回空节点。

取中点创建根节点，递归构造左右半区间并连接。

返回新树根节点。

例如原树是右链 1 -> 2 -> 3 -> 4，中序数组为 [1,2,3,4]。首个中点下标为 1，根为 2；左区间生成节点 1，右区间 [3,4] 生成根 3、右孩子 4。新树中序仍为 [1,2,3,4]，每个节点的左右高度差都不超过 1。

单节点是重要边界：build(left, right) 在 left == right 时必须创建叶子，只有 left > right 才表示空区间。

代码实现

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

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)
}

复杂度分析

时间复杂度：$O(n)$。中序遍历和重建都各访问每个节点一次。

空间复杂度：$O(n)$。有序数组与显式遍历栈最坏均为线性；构造递归栈为 $O(\log n)$。不计返回的新树仍为 $O(n)$。

关键点总结

BST 的中序序列有序，因此无需排序，也无需实现 AVL 旋转。

build(left, right) 的状态含义必须固定为闭区间；空区间条件是 left > right。

中点划分同时保证 BST 的大小关系和左右规模接近。

原树高度可能是 $O(n)$，显式栈可避免递归中序遍历在退化树上栈溢出。

新建节点可彻底摆脱旧指针；若复用节点，必须重置左右指针。

易错点总结

把前序序列当成有序序列。反例：根 2、左 1、右 3 的前序是 [2,1,3]，按中点重建会破坏 BST 性质。

空区间条件写成 left >= right 会漏掉所有单元素区间；单节点树应被构造成叶子。

子区间包含 mid 会重复使用根节点并导致递归不收缩。

初始右边界写成 values.size() 会越界；闭区间的最后下标是 size()-1。

总取左端点而非中点，[1,2,3,4] 会再次构造成链，仍不平衡。

对退化原树递归中序遍历可能产生 $O(n)$ 调用栈；显式栈规避了这个边界。

相似题目

题目	难度	考察点
108. 将有序数组转换为二叉搜索树	简单	本题的后半段，直接给出有序数组，是必须先掌握的模板
109. 有序链表转换二叉搜索树	中等	链表无法随机访问中点，需用快慢指针找中点或先转数组
110. 平衡二叉树	简单	判定而非构造，返回值兼做高度与失衡标记，用来验证本题结果正好合适
98. 验证二叉搜索树	中等	校验中序递增，需上下界随递归传递，是本题「BST 等价于中序递增」的反向应用
94. 二叉树的中序遍历	简单	中序遍历的递归与迭代写法，本题第一阶段的基本功
897. 递增顺序搜索树	简单	同样是中序重排结构，但目标是把树拉成右斜链，与本题的「压扁」方向相反
1008. 前序遍历构造二叉搜索树	中等	由前序序列反推 BST，靠值域上下界剪枝，不需要中点划分
230. 二叉搜索树中第 K 小的元素	中等	直接利用中序递增性质，中途计数即可提前返回
173. 二叉搜索树迭代器	中等	把中序遍历改造成可暂停的迭代器，栈的使用是核心
538. 把二叉搜索树转换为累加树	中等	反中序遍历累加，训练遍历顺序与题意的对应关系
426. 将二叉搜索树转化为排序的双向链表	中等	中序遍历中原地改指针，要求 $O(1)$ 额外空间，与本题「先读后建」形成对照
669. 修剪二叉搜索树	中等	按值域裁剪并重新链接，考察对 BST 性质的剪枝式利用
450. 删除二叉搜索树中的节点	中等	删除后要用后继或前驱补位，是维护 BST 结构的经典操作
105. 从前序与中序遍历序列构造二叉树	中等	同样是区间分治建树，但根的位置由前序给出而非取中点