LeetCode 1382中等BST

将二叉搜索树变平衡图解题解

这道题到底在问什么

给定一棵 BST 的根,返回一棵元素完全相同、但高度平衡的 BST。平衡指每个节点的左右子树高度差至多为 1。

输入: 右侧偏重的不平衡 BST(7 节点, 高 4)
输出: 平衡 BST(高 3),中序序列不变

最优解：一步一步想明白

3记住「先中序拉成有序数组,再每次取正中间当根、左右两半递归」,下面分两段逐帧套它。
4准备中序遍历先看原树:它右子树明显更高、整体很不平衡。第一步对它做中序遍历(左、根、右),把节点值依次收进一个数组。因为它是 BST,中序结果一定是从小到大排好的。
5已收 1 个中序遍历走到节点 10(紫色),把它的值收进数组,现在是 10。中序最先访问到的,是最左下角那个最小值。
6已收 2 个中序遍历走到节点 20(紫色),把它的值收进数组,现在是 10, 20。接着按左、根、右的顺序继续收。
7已收 3 个中序遍历走到节点 30(紫色),把它的值收进数组,现在是 10, 20, 30。接着按左、根、右的顺序继续收。
8已收 4 个中序遍历走到节点 40(紫色),把它的值收进数组,现在是 10, 20, 30, 40。接着按左、根、右的顺序继续收。
9已收 5 个中序遍历走到节点 50(紫色),把它的值收进数组,现在是 10, 20, 30, 40, 50。接着按左、根、右的顺序继续收。
10已收 6 个中序遍历走到节点 60(紫色),把它的值收进数组,现在是 10, 20, 30, 40, 50, 60。接着按左、根、右的顺序继续收。
11已收 7 个中序遍历走到节点 70(紫色),把它的值收进数组,现在是 10, 20, 30, 40, 50, 60, 70。这是最后一个、也是最大的值。
12中序遍历完成,得到有序数组 [10, 20, 30, 40, 50, 60, 70],严格升序。接下来就在这个数组上分治建树,完全不用再管原来那棵歪树的形状了。
13从整段整棵树的根:当前要处理的是区间 [0, 6](灰色是区间外、不归这棵子树管)。取正中间 m = 3,也就是值 40(绿色),让它当这棵子树的根。左边 [0, 2] 给左子树、右边 [4, 6] 给右子树。
14整棵树的根把中点 40 建成节点,接到树上当整棵树的根(紫色)。因为取的是正中间,它左边和右边的数量最接近,左右子树高度自然均衡。接着对左右两半各自递归。
15节点 40 的左孩子:当前要处理的是区间 [0, 2](灰色是区间外、不归这棵子树管)。取正中间 m = 1,也就是值 20(绿色),让它当这棵子树的根。左边 [0, 0] 给左子树、右边 [2, 2] 给右子树。
16节点 40 的左孩子把中点 20 建成节点,接到树上当节点 40 的左孩子(紫色)。因为取的是正中间,它左边和右边的数量最接近,左右子树高度自然均衡。接着对左右两半各自递归。
17节点 20 的左孩子:当前要处理的是区间 [0, 0](灰色是区间外、不归这棵子树管)。取正中间 m = 0,也就是值 10(绿色),让它当这棵子树的根。左边 [0, -1] 给左子树、右边 [1, 0] 给右子树。
18节点 20 的左孩子把中点 10 建成节点,接到树上当节点 20 的左孩子(紫色)。因为取的是正中间,它左边和右边的数量最接近,左右子树高度自然均衡。接着对左右两半各自递归。
19节点 20 的右孩子:当前要处理的是区间 [2, 2](灰色是区间外、不归这棵子树管)。取正中间 m = 2,也就是值 30(绿色),让它当这棵子树的根。左边 [2, 1] 给左子树、右边 [3, 2] 给右子树。
20节点 20 的右孩子把中点 30 建成节点,接到树上当节点 20 的右孩子(紫色)。因为取的是正中间,它左边和右边的数量最接近,左右子树高度自然均衡。接着对左右两半各自递归。
21节点 40 的右孩子:当前要处理的是区间 [4, 6](灰色是区间外、不归这棵子树管)。取正中间 m = 5,也就是值 60(绿色),让它当这棵子树的根。左边 [4, 4] 给左子树、右边 [6, 6] 给右子树。
22节点 40 的右孩子把中点 60 建成节点,接到树上当节点 40 的右孩子(紫色)。因为取的是正中间,它左边和右边的数量最接近,左右子树高度自然均衡。接着对左右两半各自递归。
23节点 60 的左孩子:当前要处理的是区间 [4, 4](灰色是区间外、不归这棵子树管)。取正中间 m = 4,也就是值 50(绿色),让它当这棵子树的根。左边 [4, 3] 给左子树、右边 [5, 4] 给右子树。
24节点 60 的左孩子把中点 50 建成节点,接到树上当节点 60 的左孩子(紫色)。因为取的是正中间,它左边和右边的数量最接近,左右子树高度自然均衡。接着对左右两半各自递归。
25节点 60 的右孩子:当前要处理的是区间 [6, 6](灰色是区间外、不归这棵子树管)。取正中间 m = 6,也就是值 70(绿色),让它当这棵子树的根。左边 [6, 5] 给左子树、右边 [7, 6] 给右子树。
26节点 60 的右孩子把中点 70 建成节点,接到树上当节点 60 的右孩子(紫色)。因为取的是正中间,它左边和右边的数量最接近,左右子树高度自然均衡。接着对左右两半各自递归。
27高度 3,左右匀称分治建完,得到一棵平衡 BST:根是 40,左右两边各挂三个节点,只有 3 层高。它的中序遍历依旧是 10, 20, 30, 40, 50, 60, 70,和原树完全一样,所以它仍是同一组值的 BST,只是变平衡了。

⚠️ 容易写错的地方

✗ 错：在原树上东挪西转想直接转平衡

✓ 对：先拉成有序数组,再从零分治建新树

直接对树做旋转又繁又易错;借中序拿到有序数组后,取中点建树简单又稳

✗ 错：建树时随便挑一个值当根

✓ 对：每次都取当前区间的正中点当根

只有取中点才能让左右两半数量最接近,从而保证高度平衡

✗ 错：build 区间边界写错(漏掉单元素或越界)

✓ 对：l > r 返回空,中点用 (l+r)/2,左 [l,m−1] 右 [m+1,r]

边界写错会漏节点或重复用值,建出的树就不对了

完整代码（Python / C++ / Java）

Python

from typing import List, Optional
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val=val; self.left=left; self.right=right
class Solution:
    def balanceBST(self, root: TreeNode) -> TreeNode:
        vals=[]
        def inorder(n):
            if n: inorder(n.left); vals.append(n.val); inorder(n.right)
        inorder(root)
        def build(l,r):
            if l>r: return None
            m=(l+r)//2; node=TreeNode(vals[m]); node.left=build(l,m-1); node.right=build(m+1,r); return node
        return build(0,len(vals)-1)

C++

#include <algorithm>
#include <functional>
#include <queue>
#include <string>
#include <unordered_map>
#include <vector>
using namespace std;
struct TreeNode{int val;TreeNode* left;TreeNode* right;TreeNode():val(0),left(nullptr),right(nullptr){} TreeNode(int x):val(x),left(nullptr),right(nullptr){} TreeNode(int x,TreeNode*l,TreeNode*r):val(x),left(l),right(r){}};
class Solution{public: TreeNode* balanceBST(TreeNode* root){ vector<int> vals; function<void(TreeNode*)> in=[&](TreeNode*n){ if(!n)return; in(n->left); vals.push_back(n->val); in(n->right);}; in(root); function<TreeNode*(int,int)> build=[&](int l,int r){ if(l>r)return (TreeNode*)nullptr; int m=(l+r)/2; auto n=new TreeNode(vals[m]); n->left=build(l,m-1); n->right=build(m+1,r); return n;}; return build(0,vals.size()-1); }};

Java

import java.util.*;
class TreeNode{int val;TreeNode left,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{ ArrayList<Integer> vals; public TreeNode balanceBST(TreeNode root){ vals=new ArrayList<>(); in(root); return build(0,vals.size()-1);} void in(TreeNode n){ if(n==null)return; in(n.left); vals.add(n.val); in(n.right);} TreeNode build(int l,int r){ if(l>r)return null; int m=(l+r)/2; TreeNode n=new TreeNode(vals.get(m)); n.left=build(l,m-1); n.right=build(m+1,r); return n;} }

复杂度

时间

O(n)

中序遍历每个节点一次 O(n);分治建树每个值恰好被选为某棵子树的根一次,也是 O(n)

空间

O(n)

有序数组占 O(n);中序遍历在原不平衡树上递归栈最坏 O(h) 可达 O(n),建树递归栈 O(log n);数组主导,合起来 O(n)

看不够？换成动画再走一遍

上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着将二叉搜索树变平衡的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。

看交互动画版 →更多图解题

面试官可能追问

能不能不用额外数组、直接在树上转成平衡?+

可以,但麻烦得多。一种是 Day–Stout–Warren(DSW)算法:先把 BST 旋转成一条「藤蔓」(右单链),再通过一连串旋转压成平衡树,能做到 O(1) 额外空间。不过它的旋转逻辑比「中序 + 取中点分治」难写得多,面试里除非特别要求 O(1) 空间,一般首选中序加分治这版,清晰又不易错。

取中点时 (l+r)/2 取到的是偏左还是偏右?有影响吗?+

(l+r)/2 是向下取整,偶数个元素时取偏左那个。这对结果没有本质影响:取偏左或偏右都能得到一棵合法的平衡 BST,只是左右子树的形状略有不同,高度都满足平衡要求。题目不要求唯一形态,所以两种都对。

想听吴师兄把这道题讲给你听？

文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把将二叉搜索树变平衡一步步讲透（全站 0 节语音精讲，持续扩充），卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。

¥99 开通图解算法年卡 →先去动画页听 30 秒试听 →

本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。

LeetCode 1382中等BST

将二叉搜索树变平衡图解题解

这道题到底在问什么

给定一棵 BST 的根,返回一棵元素完全相同、但高度平衡的 BST。平衡指每个节点的左右子树高度差至多为 1。

输入: 右侧偏重的不平衡 BST(7 节点, 高 4)
输出: 平衡 BST(高 3),中序序列不变

最优解：一步一步想明白

3记住「先中序拉成有序数组,再每次取正中间当根、左右两半递归」,下面分两段逐帧套它。
4准备中序遍历先看原树:它右子树明显更高、整体很不平衡。第一步对它做中序遍历(左、根、右),把节点值依次收进一个数组。因为它是 BST,中序结果一定是从小到大排好的。
5已收 1 个中序遍历走到节点 10(紫色),把它的值收进数组,现在是 10。中序最先访问到的,是最左下角那个最小值。
6已收 2 个中序遍历走到节点 20(紫色),把它的值收进数组,现在是 10, 20。接着按左、根、右的顺序继续收。
7已收 3 个中序遍历走到节点 30(紫色),把它的值收进数组,现在是 10, 20, 30。接着按左、根、右的顺序继续收。
8已收 4 个中序遍历走到节点 40(紫色),把它的值收进数组,现在是 10, 20, 30, 40。接着按左、根、右的顺序继续收。
9已收 5 个中序遍历走到节点 50(紫色),把它的值收进数组,现在是 10, 20, 30, 40, 50。接着按左、根、右的顺序继续收。
10已收 6 个中序遍历走到节点 60(紫色),把它的值收进数组,现在是 10, 20, 30, 40, 50, 60。接着按左、根、右的顺序继续收。
11已收 7 个中序遍历走到节点 70(紫色),把它的值收进数组,现在是 10, 20, 30, 40, 50, 60, 70。这是最后一个、也是最大的值。
12中序遍历完成,得到有序数组 [10, 20, 30, 40, 50, 60, 70],严格升序。接下来就在这个数组上分治建树,完全不用再管原来那棵歪树的形状了。
13从整段整棵树的根:当前要处理的是区间 [0, 6](灰色是区间外、不归这棵子树管)。取正中间 m = 3,也就是值 40(绿色),让它当这棵子树的根。左边 [0, 2] 给左子树、右边 [4, 6] 给右子树。
14整棵树的根把中点 40 建成节点,接到树上当整棵树的根(紫色)。因为取的是正中间,它左边和右边的数量最接近,左右子树高度自然均衡。接着对左右两半各自递归。
15节点 40 的左孩子:当前要处理的是区间 [0, 2](灰色是区间外、不归这棵子树管)。取正中间 m = 1,也就是值 20(绿色),让它当这棵子树的根。左边 [0, 0] 给左子树、右边 [2, 2] 给右子树。
16节点 40 的左孩子把中点 20 建成节点,接到树上当节点 40 的左孩子(紫色)。因为取的是正中间,它左边和右边的数量最接近,左右子树高度自然均衡。接着对左右两半各自递归。
17节点 20 的左孩子:当前要处理的是区间 [0, 0](灰色是区间外、不归这棵子树管)。取正中间 m = 0,也就是值 10(绿色),让它当这棵子树的根。左边 [0, -1] 给左子树、右边 [1, 0] 给右子树。
18节点 20 的左孩子把中点 10 建成节点,接到树上当节点 20 的左孩子(紫色)。因为取的是正中间,它左边和右边的数量最接近,左右子树高度自然均衡。接着对左右两半各自递归。
19节点 20 的右孩子:当前要处理的是区间 [2, 2](灰色是区间外、不归这棵子树管)。取正中间 m = 2,也就是值 30(绿色),让它当这棵子树的根。左边 [2, 1] 给左子树、右边 [3, 2] 给右子树。
20节点 20 的右孩子把中点 30 建成节点,接到树上当节点 20 的右孩子(紫色)。因为取的是正中间,它左边和右边的数量最接近,左右子树高度自然均衡。接着对左右两半各自递归。
21节点 40 的右孩子:当前要处理的是区间 [4, 6](灰色是区间外、不归这棵子树管)。取正中间 m = 5,也就是值 60(绿色),让它当这棵子树的根。左边 [4, 4] 给左子树、右边 [6, 6] 给右子树。
22节点 40 的右孩子把中点 60 建成节点,接到树上当节点 40 的右孩子(紫色)。因为取的是正中间,它左边和右边的数量最接近,左右子树高度自然均衡。接着对左右两半各自递归。
23节点 60 的左孩子:当前要处理的是区间 [4, 4](灰色是区间外、不归这棵子树管)。取正中间 m = 4,也就是值 50(绿色),让它当这棵子树的根。左边 [4, 3] 给左子树、右边 [5, 4] 给右子树。
24节点 60 的左孩子把中点 50 建成节点,接到树上当节点 60 的左孩子(紫色)。因为取的是正中间,它左边和右边的数量最接近,左右子树高度自然均衡。接着对左右两半各自递归。
25节点 60 的右孩子:当前要处理的是区间 [6, 6](灰色是区间外、不归这棵子树管)。取正中间 m = 6,也就是值 70(绿色),让它当这棵子树的根。左边 [6, 5] 给左子树、右边 [7, 6] 给右子树。
26节点 60 的右孩子把中点 70 建成节点,接到树上当节点 60 的右孩子(紫色)。因为取的是正中间,它左边和右边的数量最接近,左右子树高度自然均衡。接着对左右两半各自递归。
27高度 3,左右匀称分治建完,得到一棵平衡 BST:根是 40,左右两边各挂三个节点,只有 3 层高。它的中序遍历依旧是 10, 20, 30, 40, 50, 60, 70,和原树完全一样,所以它仍是同一组值的 BST,只是变平衡了。

⚠️ 容易写错的地方

✗ 错：在原树上东挪西转想直接转平衡

✓ 对：先拉成有序数组,再从零分治建新树

直接对树做旋转又繁又易错;借中序拿到有序数组后,取中点建树简单又稳

✗ 错：建树时随便挑一个值当根

✓ 对：每次都取当前区间的正中点当根

只有取中点才能让左右两半数量最接近,从而保证高度平衡

✗ 错：build 区间边界写错(漏掉单元素或越界)

✓ 对：l > r 返回空,中点用 (l+r)/2,左 [l,m−1] 右 [m+1,r]

边界写错会漏节点或重复用值,建出的树就不对了

完整代码（Python / C++ / Java）

Python

from typing import List, Optional
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val=val; self.left=left; self.right=right
class Solution:
    def balanceBST(self, root: TreeNode) -> TreeNode:
        vals=[]
        def inorder(n):
            if n: inorder(n.left); vals.append(n.val); inorder(n.right)
        inorder(root)
        def build(l,r):
            if l>r: return None
            m=(l+r)//2; node=TreeNode(vals[m]); node.left=build(l,m-1); node.right=build(m+1,r); return node
        return build(0,len(vals)-1)

C++

#include <algorithm>
#include <functional>
#include <queue>
#include <string>
#include <unordered_map>
#include <vector>
using namespace std;
struct TreeNode{int val;TreeNode* left;TreeNode* right;TreeNode():val(0),left(nullptr),right(nullptr){} TreeNode(int x):val(x),left(nullptr),right(nullptr){} TreeNode(int x,TreeNode*l,TreeNode*r):val(x),left(l),right(r){}};
class Solution{public: TreeNode* balanceBST(TreeNode* root){ vector<int> vals; function<void(TreeNode*)> in=[&](TreeNode*n){ if(!n)return; in(n->left); vals.push_back(n->val); in(n->right);}; in(root); function<TreeNode*(int,int)> build=[&](int l,int r){ if(l>r)return (TreeNode*)nullptr; int m=(l+r)/2; auto n=new TreeNode(vals[m]); n->left=build(l,m-1); n->right=build(m+1,r); return n;}; return build(0,vals.size()-1); }};

Java

import java.util.*;
class TreeNode{int val;TreeNode left,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{ ArrayList<Integer> vals; public TreeNode balanceBST(TreeNode root){ vals=new ArrayList<>(); in(root); return build(0,vals.size()-1);} void in(TreeNode n){ if(n==null)return; in(n.left); vals.add(n.val); in(n.right);} TreeNode build(int l,int r){ if(l>r)return null; int m=(l+r)/2; TreeNode n=new TreeNode(vals.get(m)); n.left=build(l,m-1); n.right=build(m+1,r); return n;} }

复杂度

时间

O(n)

中序遍历每个节点一次 O(n);分治建树每个值恰好被选为某棵子树的根一次,也是 O(n)

空间

O(n)

有序数组占 O(n);中序遍历在原不平衡树上递归栈最坏 O(h) 可达 O(n),建树递归栈 O(log n);数组主导,合起来 O(n)

看不够？换成动画再走一遍

上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着将二叉搜索树变平衡的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。

看交互动画版 →更多图解题

面试官可能追问

能不能不用额外数组、直接在树上转成平衡?+

取中点时 (l+r)/2 取到的是偏左还是偏右?有影响吗?+

想听吴师兄把这道题讲给你听？

¥99 开通图解算法年卡 →先去动画页听 30 秒试听 →

将二叉搜索树变平衡 图解题解

这道题到底在问什么

最优解：一步一步想明白

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

Python

C++

Java

复杂度

看不够？换成动画再走一遍

面试官可能追问

想听吴师兄把这道题讲给你听？

将二叉搜索树变平衡 图解题解

这道题到底在问什么

最优解：一步一步想明白

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

Python

C++

Java

复杂度

看不够？换成动画再走一遍

面试官可能追问

想听吴师兄把这道题讲给你听？

将二叉搜索树变平衡图解题解

将二叉搜索树变平衡图解题解