# 99. 恢复二叉搜索树 (Medium)

## 问题描述

[99. 恢复二叉搜索树][link] (Medium)

[link]: https://leetcode.cn/problems/recover-binary-search-tree/

给你二叉搜索树的根节点 `root` ，该树中的 **恰好** 两个节点的值被错误地交换。请在不改变其结构的情况下
，恢复这棵树 。

**示例 1：**

![](https://pic-upyun.zwyyy456.tech/smms/2023-12-26-65516.jpg)

```
输入：root = [1,3,null,null,2]
输出：[3,1,null,null,2]
解释：3 不能是 1 的左孩子，因为 3 > 1 。交换 1 和 3 使二叉搜索树有效。
```

**示例 2：**

![](https://pic-upyun.zwyyy456.tech/smms/2023-12-26-065516.jpg)

```
输入：root = [3,1,4,null,null,2]
输出：[2,1,4,null,null,3]
解释：2 不能在 3 的右子树中，因为 2 < 3 。交换 2 和 3 使二叉搜索树有效。
```

**提示：**

- 树上节点的数目在范围 `[2, 1000]` 内
- `-2³¹ <= Node.val <= 2³¹ - 1`

**进阶：** 使用 `O(n)` 空间复杂度的解法很容易实现。你能想出一个只使用 `O(1)` 空间的解决方案吗？

## 解题思路

这里就直接考虑 $O(1)$ 时间复杂度的解法了，首先我们知道，对二叉搜索树进行中序遍历，其结点值是严格递增的，因此，我们可以利用这一点来找出被交换的两个节点。

我们考虑一个递增序列，然后交换序列中任意两个元素，如果这两个元素是相邻的，那么当我们遍历时，会出现一次 $a_{i} < a_{i - 1}$ 的情况；而如果这两个元素不相邻，那么会出现两次 $a_{i} < a_{i - 1}$ 的情况。我们将出现 $a_{i} < a_{i - 1}$ 的元素对都存入数组 `vec`，那么 `vec.size() == 2 || vec.size() == 4`，我们交换数组的首元素与尾元素的值即可。

我们在中序遍历时，可以用 `prev` 表示遍历的上一个节点的指针，比较 `root->val` 与 `pre->val` 的值，判断序列是否严格递增，如果不是，将 `root` 和 `pre` 依次 `push_back` 到 vec 中去，最后交换 `vec[0]->val` 和 `vec.back()->val`。

带 `prev` 的中序遍历的模板如下：

```cpp
void midtra(TreeNode *root, TreeNode **prev) {
    if (root == nullptr) {
        return;
    }
    midtra(root->left, prev);
    *prev = root;
    midtra(root->right, prev);
}
```

## 代码
```cpp
class Solution {
  public:
    void midtra(TreeNode *root, TreeNode **prev, vector<TreeNode *> &wrong) {
        if (root == nullptr) {
            return;
        }
        midtra(root->left, prev, wrong);
        if (*prev != nullptr) {
            if (root->val < (*prev)->val) {
                wrong.push_back(*prev);
                wrong.push_back(root);
            }
        }
        *prev = root;
        midtra(root->right, prev, wrong);
    }
    void recoverTree(TreeNode *root) {
        // 中序遍历
        vector<TreeNode *> wrong;
        TreeNode *node = nullptr;
        midtra(root, &node, wrong);
        swap(wrong[0]->val, wrong.back()->val);
    }
};
```