问题描述 链接到标题

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

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

示例 1：

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

示例 2：

输入：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 的中序遍历的模板如下：

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

代码 链接到标题 

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);
    }
};