题目描述
思路解析动画文字版
记住「先中序拉成有序数组,再每次取正中间当根、左右两半递归」,下面分两段逐帧套它。
原树(不平衡)：先看原树:它右子树明显更高、整体很不平衡。第一步对它做中序遍历(左、根、右),把节点值依次收进一个数组。因为它是 BST,中序结果一定是从小到大排好的。
中序访问 10：中序遍历走到节点 10(紫色),把它的值收进数组,现在是 10。中序最先访问到的,是最左下角那个最小值。
中序访问 20：中序遍历走到节点 20(紫色),把它的值收进数组,现在是 10, 20。接着按 左、根、右 的顺序继续收。
中序访问 30：中序遍历走到节点 30(紫色),把它的值收进数组,现在是 10, 20, 30。接着按 左、根、右 的顺序继续收。
中序访问 40：中序遍历走到节点 40(紫色),把它的值收进数组,现在是 10, 20, 30, 40。接着按 左、根、右 的顺序继续收。
中序访问 50：中序遍历走到节点 50(紫色),把它的值收进数组,现在是 10, 20, 30, 40, 50。接着按 左、根、右 的顺序继续收。
中序访问 60：中序遍历走到节点 60(紫色),把它的值收进数组,现在是 10, 20, 30, 40, 50, 60。接着按 左、根、右 的顺序继续收。
中序访问 70：中序遍历走到节点 70(紫色),把它的值收进数组,现在是 10, 20, 30, 40, 50, 60, 70。这是最后一个、也是最大的值。
中序遍历完成,得到有序数组 [10, 20, 30, 40, 50, 60, 70],严格升序。接下来就在这个数组上分治建树,完全不用再管原来那棵歪树的形状了。
从整段 整棵树的根:当前要处理的是区间 [0, 6](灰色是区间外、不归这棵子树管)。取正中间 m = 3,也就是值 40(绿色),让它当这棵子树的根。左边 [0, 2] 给左子树、右边 [4, 6] 给右子树。
建节点 40：把中点 40 建成节点,接到树上当整棵树的根(紫色)。因为取的是正中间,它左边和右边的数量最接近,左右子树高度自然均衡。接着对左右两半各自递归。
节点 40 的左孩子:当前要处理的是区间 [0, 2](灰色是区间外、不归这棵子树管)。取正中间 m = 1,也就是值 20(绿色),让它当这棵子树的根。左边 [0, 0] 给左子树、右边 [2, 2] 给右子树。
建节点 20：把中点 20 建成节点,接到树上当节点 40 的左孩子(紫色)。因为取的是正中间,它左边和右边的数量最接近,左右子树高度自然均衡。接着对左右两半各自递归。
节点 20 的左孩子:当前要处理的是区间 [0, 0](灰色是区间外、不归这棵子树管)。取正中间 m = 0,也就是值 10(绿色),让它当这棵子树的根。左边 [0, -1] 给左子树、右边 [1, 0] 给右子树。
建节点 10：把中点 10 建成节点,接到树上当节点 20 的左孩子(紫色)。因为取的是正中间,它左边和右边的数量最接近,左右子树高度自然均衡。接着对左右两半各自递归。
节点 20 的右孩子:当前要处理的是区间 [2, 2](灰色是区间外、不归这棵子树管)。取正中间 m = 2,也就是值 30(绿色),让它当这棵子树的根。左边 [2, 1] 给左子树、右边 [3, 2] 给右子树。
建节点 30：把中点 30 建成节点,接到树上当节点 20 的右孩子(紫色)。因为取的是正中间,它左边和右边的数量最接近,左右子树高度自然均衡。接着对左右两半各自递归。
节点 40 的右孩子:当前要处理的是区间 [4, 6](灰色是区间外、不归这棵子树管)。取正中间 m = 5,也就是值 60(绿色),让它当这棵子树的根。左边 [4, 4] 给左子树、右边 [6, 6] 给右子树。
建节点 60：把中点 60 建成节点,接到树上当节点 40 的右孩子(紫色)。因为取的是正中间,它左边和右边的数量最接近,左右子树高度自然均衡。接着对左右两半各自递归。
节点 60 的左孩子:当前要处理的是区间 [4, 4](灰色是区间外、不归这棵子树管)。取正中间 m = 4,也就是值 50(绿色),让它当这棵子树的根。左边 [4, 3] 给左子树、右边 [5, 4] 给右子树。
建节点 50：把中点 50 建成节点,接到树上当节点 60 的左孩子(紫色)。因为取的是正中间,它左边和右边的数量最接近,左右子树高度自然均衡。接着对左右两半各自递归。
节点 60 的右孩子:当前要处理的是区间 [6, 6](灰色是区间外、不归这棵子树管)。取正中间 m = 6,也就是值 70(绿色),让它当这棵子树的根。左边 [6, 5] 给左子树、右边 [7, 6] 给右子树。
建节点 70：把中点 70 建成节点,接到树上当节点 60 的右孩子(紫色)。因为取的是正中间,它左边和右边的数量最接近,左右子树高度自然均衡。接着对左右两半各自递归。
平衡完成：分治建完,得到一棵平衡 BST:根是 40,左右两边各挂三个节点,只有 3 层高。它的中序遍历依旧是 10, 20, 30, 40, 50, 60, 70,和原树完全一样,所以它仍是同一组值的 BST,只是变平衡了。
边界:空树空数组、单节点照旧、本就平衡也能重建。
两个追问:DSW 可省数组但难写;中点偏左偏右都平衡。
参考代码
from typing import List, Optionalclass TreeNode: def __init__(self, val=0, left=None, right=None): self.val=val; self.left=left; self.right=rightclass 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)复杂度
- 时间：O(n)，中序遍历每个节点一次 O(n);分治建树每个值恰好被选为某棵子树的根一次,也是 O(n)
- 空间：O(n)，有序数组占 O(n);中序遍历在原不平衡树上递归栈最坏 O(h) 可达 O(n),建树递归栈 O(log n);数组主导,合起来 O(n)
易错点
面试追问把动画讲成自己的话
追问能不能不用额外数组、直接在树上转成平衡?
追问取中点时 (l+r)/2 取到的是偏左还是偏右?有影响吗?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。再去主线里挑下一道练手。
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题