恢复二叉搜索树 图解题解

这道题到底在问什么

输入

中序应 10,20,30,40,50,60,70,实际 10,60,30,40,50,20,70

输出

把 60 与 20 换回

输入

相邻两节点被换

输出

只有一处逆序,交换这一对

最优解：一步一步想明白

1. 3记住「中序升序被破坏 → 抓逆序对 → first 是第一处的大者、second 是最后一处的小者 → 交换两个值」,下面逐帧套它。
2. 4中序 = 升序先找感觉:一棵合法 BST(根 40、左 20、右 60),中序遍历是 20、40、60,严格升序。我们要恢复的那棵,中序却乱了序,顺着这个破绽就能揪出放错的两个节点。
3. 5中序乱序这就是待恢复的树。光看树形不好看出哪里错,但只要走一遍中序,升序一被打破就露馅。下面开始中序遍历,一个节点一个节点地比。
4. 6从最左下开始中序遍历的顺序是「左子树 → 根 → 右子树」,所以第一个访问到的是整棵树最左下角的节点。prev、first、second 现在都为空,开始逐个走、逐个比。
5. 7到达 值10中序走到节点 值10(紫色)。它是中序的第一个,前面没有 prev 可比,直接收下。
6. 8记下 值10值10 成为目前中序的开头,把 prev 更新成它,继续往后走。
7. 9到达 值60中序走到节点 值60(紫色)。要拿它和 prev = 值10 比一比,看是不是还在升序。
8. 10仍升序值60 不小于前一个,序列仍然升序,没有逆序。把 prev 更新成 值60,接着走。
9. 11到达 值30中序走到节点 值30(紫色)。要拿它和 prev = 值60 比一比,看是不是还在升序。
10. 12值60 > 值30逆序出现!prev = 值60 竟然大于当前 值30(标红)。这是第一处逆序,把较大的 prev = 值60 记为 first;两种情况都把较小的当前节点 值30 记为 second。
11. 13到达 值40中序走到节点 值40(紫色)。要拿它和 prev = 值30 比一比,看是不是还在升序。
12. 14仍升序值40 不小于前一个,序列仍然升序,没有逆序。把 prev 更新成 值40,接着走。
13. 15到达 值50中序走到节点 值50(紫色)。要拿它和 prev = 值40 比一比,看是不是还在升序。
14. 16仍升序值50 不小于前一个,序列仍然升序,没有逆序。把 prev 更新成 值50,接着走。
15. 17到达 值20中序走到节点 值20(紫色)。要拿它和 prev = 值50 比一比,看是不是还在升序。
16. 18值50 > 值20逆序出现!prev = 值50 竟然大于当前 值20(标红)。这是第二处逆序,first 保持不动;两种情况都把较小的当前节点 值20 记为 second。
17. 19到达 值70中序走到节点 值70(紫色)。要拿它和 prev = 值20 比一比,看是不是还在升序。
18. 20仍升序值70 不小于前一个,序列仍然升序,没有逆序。把 prev 更新成 值70,接着走。
19. 21first 值60 · second 值20遍历结束,两处逆序把放错的两个节点都揪了出来(标红):first = 值60、second = 值20。它们正是当初被对调的那一对,只要把两个节点的值换回来就恢复了。
20. 22值60 ↔ 值20只交换这两个节点里的值(绿色),树的结构一点没动。原来 first 处的 值60 和 second 处的 值20 互换,现在它们归位了。
21. 23中序重新升序再走一遍中序:10、20、30、40、50、60、70,严格升序,逆序对全没了,BST 恢复成功。整个过程只比较、不挪结构,空间用在递归栈上。

⚠️ 容易写错的地方

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

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

#include <algorithm>
#include <functional>
#include <string>
#include <unordered_map>
#include <unordered_set>
#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{TreeNode* first=nullptr;TreeNode* second=nullptr;TreeNode* prev=nullptr; public: void recoverTree(TreeNode* root){ first=second=prev=nullptr; dfs(root); if(first&&second)swap(first->val,second->val);} void dfs(TreeNode*n){ if(!n)return; dfs(n->left); if(prev&&prev->val>n->val){ if(!first)first=prev; second=n;} prev=n; dfs(n->right);} };

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{ TreeNode first,second,prev; public void recoverTree(TreeNode root){ first=second=prev=null; dfs(root); if(first!=null&&second!=null){ int t=first.val; first.val=second.val; second.val=t; } } void dfs(TreeNode n){ if(n==null)return; dfs(n.left); if(prev!=null&&prev.val>n.val){ if(first==null)first=prev; second=n; } prev=n; dfs(n.right);} }

复杂度

面试官可能追问