题目描述
思路解析动画文字版
记住「中序升序被破坏 → 抓逆序对 → first 是第一处的大者、second 是最后一处的小者 → 交换两个值」,下面逐帧套它。
BST 性质：先找感觉:一棵合法 BST(根 40、左 20、右 60),中序遍历是 20、40、60,严格升序。我们要恢复的那棵,中序却乱了序,顺着这个破绽就能揪出放错的两个节点。
待恢复的树：这就是待恢复的树。光看树形不好看出哪里错,但只要走一遍中序,升序一被打破就露馅。下面开始中序遍历,一个节点一个节点地比。
开始中序：中序遍历的顺序是「左子树 → 根 → 右子树」,所以第一个访问到的是整棵树最左下角的节点。prev、first、second 现在都为空,开始逐个走、逐个比。
中序第 1 个：中序走到节点 值10(紫色)。它是中序的第一个,前面没有 prev 可比,直接收下。
中序第 1 个：值10 成为目前中序的开头,把 prev 更新成它,继续往后走。
中序第 2 个：中序走到节点 值60(紫色)。要拿它和 prev = 值10 比一比,看是不是还在升序。
中序第 2 个：值60 不小于前一个,序列仍然升序,没有逆序。把 prev 更新成 值60,接着走。
中序第 3 个：中序走到节点 值30(紫色)。要拿它和 prev = 值60 比一比,看是不是还在升序。
逆序对!：逆序出现!prev = 值60 竟然大于当前 值30(标红)。这是第一处逆序,把较大的 prev = 值60 记为 first;两种情况都把较小的当前节点 值30 记为 second。
中序第 4 个：中序走到节点 值40(紫色)。要拿它和 prev = 值30 比一比,看是不是还在升序。
中序第 4 个：值40 不小于前一个,序列仍然升序,没有逆序。把 prev 更新成 值40,接着走。
中序第 5 个：中序走到节点 值50(紫色)。要拿它和 prev = 值40 比一比,看是不是还在升序。
中序第 5 个：值50 不小于前一个,序列仍然升序,没有逆序。把 prev 更新成 值50,接着走。
中序第 6 个：中序走到节点 值20(紫色)。要拿它和 prev = 值50 比一比,看是不是还在升序。
逆序对!：逆序出现!prev = 值50 竟然大于当前 值20(标红)。这是第二处逆序,first 保持不动;两种情况都把较小的当前节点 值20 记为 second。
中序第 7 个：中序走到节点 值70(紫色)。要拿它和 prev = 值20 比一比,看是不是还在升序。
中序第 7 个：值70 不小于前一个,序列仍然升序,没有逆序。把 prev 更新成 值70,接着走。
两点已锁定：遍历结束,两处逆序把放错的两个节点都揪了出来(标红):first = 值60、second = 值20。它们正是当初被对调的那一对,只要把两个节点的值换回来就恢复了。
交换两个值：只交换这两个节点里的值(绿色),树的结构一点没动。原来 first 处的 值60 和 second 处的 值20 互换,现在它们归位了。
恢复完成 · 验证：再走一遍中序:10、20、30、40、50、60、70,严格升序,逆序对全没了,BST 恢复成功。整个过程只比较、不挪结构,空间用在递归栈上。
边界:相邻=一处逆序、非相邻=两处逆序;统一用「first 第一次、second 每次」覆盖两种。
两个高频追问:Morris 中序做 O(1) 空间;只换值以保持结构。
参考代码
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 recoverTree(self, root: Optional[TreeNode]) -> None: first = second = prev = None def dfs(node): nonlocal first, second, prev if not node: return dfs(node.left) if prev and prev.val > node.val: if not first: first = prev second = node prev = node dfs(node.right) dfs(root) if first and second: first.val, second.val = second.val, first.val复杂度
- 时间：O(n)，中序遍历每个节点恰好访问一次,n 是节点数;末尾交换是 O(1)
- 空间：O(h)，递归栈深度等于树高 h,最坏退化成链时 O(n);用 Morris 中序可降到 O(1)
易错点
面试追问把动画讲成自己的话
追问能不能做到 O(1) 额外空间?
追问为什么只交换值、不交换节点?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。再去主线里挑下一道练手。
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题