99. 恢复二叉搜索树

题意

给你二叉搜索树的根节点 root ，该树中 恰好 有两个节点的值被错误地交换。请在不改变

其结构的情况下，恢复这棵树 。

难度

中等

示例

示例 1：

099.%E6%81%A2%E5%A4%8D%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6

%A0%91-20231110085147.png

输入：root = [1,3,null,null,2]

输出：[3,1,null,null,2]

解释：3 不能是 1 的左孩子，因为 3 > 1 。交换 1 和 3 使二叉搜索树有效。

示例 2：

099.%E6%81%A2%E5%A4%8D%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6

%A0%91-20231110085213.png

输入：root = [3,1,4,null,null,2]

输出：[2,1,4,null,null,3]

解释：2 不能在 3 的右子树中，因为 2 < 3 。交换 2 和 3 使二叉搜索树有效。

分析

二叉搜索树一个重要的特点就是：中序遍历必然是一个单调递增的序列。

还记得中序遍历吧？

我们在 094.二叉树的中序遍历中曾经提到过，中序遍历是二叉树遍历的一种，它的遍历

顺序为：左子树——>根节点——>右子树。

那为什么中序遍历必然是一个单调递增的序列呢？

因为中序遍历是先遍历左子树的，而左子树的值都比当前节点的小，然后是当前节点，再

然后遍历右子树，而右子树的值又比当前节点的大。

很显然，如果有两个节点的位置恰好被错误的交换，那么中序遍历的时候，单调递增的特

征就会被破坏掉，而此时，我们只需要找出这两个错误调换的节点，就能恢复二叉搜索树

了。

具体怎么实现呢？

还是要依靠递归来帮忙（上一节我们还重点强调过）。

我们首先来中序遍历整个二叉搜索树。

接着从序列中找到 nums[i] > nums[i + 1]的地方，因为正常的序列为递增序列，出现反

常的地方，必然是交换的地方。

这样我们便可以找出交换过的节点，下一步，交换这个两个节点就能恢复原始的二叉搜索

树了。

这次还是使用一次遍历，找到错误交换的两个节点，直接交换其位置即可。

一共三次遍历，第一次是中序遍历求序列，第二次是找调换位置，第三次是遍历二叉搜索

树修改对应节点。

/**

* Definition for a binary tree node.

* public class TreeNode {

* int val;

* TreeNode left;

* TreeNode 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 {

private ArrayList<Integer> midTravel = new ArrayList<>(); // 用来存储中序遍历

的结果

public void recoverTree(TreeNode root) {

if (root == null) { // 如果根节点为空，则不需要恢复，直接返回

return;

}

middleTravel(root); // 执行中序遍历

int[] nums = findPosition(); // 找到被错误交换的两个节点的值

checkTravel(root, nums[0], nums[1]); // 再次遍历树，修复这两个节点的值

}

// 中序遍历的辅助方法，用于读取节点的值

public void read(TreeNode pos) {

midTravel.add(pos.val);

}

// 中序遍历，获得整个二叉树的顺序

public void middleTravel(TreeNode pos) {

if (pos == null) {

return;

}

middleTravel(pos.left); // 遍历左子树

read(pos); // 读取当前节点

middleTravel(pos.right); // 遍历右子树

}

 // 找出交换的元素，返回被错误交换的两个节点的值

public int[] findPosition() {

int siz = midTravel.size(); // 中序遍历结果的大小

int pos1 = -1, pos2 = -1; // 初始化两个节点位置

for (int i = 0; i < siz - 1; i++) {

// 如果当前节点值大于下一个节点值，说明找到了一个被交换的节点

if (midTravel.get(i + 1) < midTravel.get(i)) {

pos2 = i + 1;

if (pos1 == -1) {

pos1 = i; // 记录第一个被交换的节点位置

}

}

}

return new int[]{midTravel.get(pos1), midTravel.get(pos2)}; // 返回两个被交换

节点的值

}

// 修改元素，修复树结构

public void checkTravel(TreeNode pos, int num1, int num2) {

if (pos == null) {

return;

}

// 如果当前节点值是被交换的值之一，则将它修复为正确的值

if (pos.val == num1) {

pos.val = num2;

} else if (pos.val == num2) {

pos.val = num1;

}

// 递归遍历左右子树

checkTravel(pos.left, num1, num2);

checkTravel(pos.right, num1, num2);

}

}

一共有三个主要的步骤：

1. 中序遍历二叉搜索树，得到一个升序的数列。

2. 使用中序遍历找到二叉搜索树中顺序错误的两个节点。在正常情况下，中序遍历二叉

搜索树应该得到一个升序的数列。如果有两个数的顺序被交换了，那么就会出现两处

顺序错误：第一处是较大的数与它后面的一个较小的数交换了位置，第二处是较小的

数与它后面的一个较大的数交换了位置。

3. 再次遍历树，修复这两个节点的值。遍历时检查每个节点的值，如果与被交换的两个

值中的任何一个匹配，就将其替换为另一个。这样就能保证这两个节点的值被交换回

来，从而恢复二叉搜索树的性质。

来看一下题解效率：

099.%E6%81%A2%E5%A4%8D%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6

%A0%91-20231110091313.png

总结

AVL 树是二叉搜索树（BST）的一种，所以它继承了 BST 的所有特性。在 AVL 树中，对

于任意节点，其左子树中的所有值都小于该节点的值，其右子树中的所有值都大于该节点

的值。

本题并不要求我们处理或者维持 AVL 树的平衡，但在处理 BST 时理解其性质和可能的操

作（如旋转）对于解决相关问题是有帮助的。

力扣链接：https://leetcode.cn/problems/recover-binary-search-tree/