给你二叉搜索树的根节点 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] 内
-231 <= Node.val <= 231 - 1
 
​

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/recover-binary-search-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
​

显示中序遍历

看到二叉搜索树就应该联想到中序遍历，而对于一个恰好换了两个点值的结点，我们观察两个样例的中序遍历
[3, 2, 1]
[1, 3 ,2 ,4]
可以看到样例的中序遍历的乱序的两个点，第一个点是从左往右数第一个逆序的，而第二个点是从右往左数第一个逆序的，所以我们可以先求得二叉树的中序遍历 然后分别从左和右遍历一次取出逆序的点。

/**
 * Definition for a binary tree node.
 * 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 *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> inOrders;
    void inOrder(TreeNode* node){
        if(node == nullptr){
            return;
        }
        inOrder(node->left);
        inOrders.push_back(node->val);
        inOrder(node->right);
    }
    void recoverTree(TreeNode* root) {
        inOrder(root);
        int x = 0, y = inOrders.size() - 1;
        // 找左边的
        for(int i = 1; i < inOrders.size(); i++){
            if(inOrders[i] > inOrders[i-1]){
                continue;
            }
            x = inOrders[i - 1];
            break;
        }
        // 找右边的
        for(int i = y - 1; i >= 0; i--){
            if(inOrders[i] < inOrders[i+1]){
                continue;
            }
            y = inOrders[i + 1];
            break;
        }
        shitTree(root, x, y);
    }
    void shitTree(TreeNode* node, int x, int y){
        if(node == nullptr){
            return;
        }
        shitTree(node->left, x, y);
        shitTree(node->right, x, y);
        if(node->val == x || node->val == y) {
            node->val = node->val == x ? y : x;
        }
    }
};

隐式中序遍历

进一步分析我们似乎不用存整个中序遍历，因为实际只需要存当前中序的值与上一次中序的值进行比较，这里有一个点若第一个点没有找到时，找到一个逆序的点时就可以赋值x与y，【但是】如果后续再遇到乱序的话要把y设为当前结点？为什么？观察第一个样例数据的中序遍历
[3, 2, 1]
这种情况是要1与3进行交换。若是2与3进行交换的话得到的是[2, 3, 1] 还是逆序的，也就是说逆序的时候第二个点要找尽可能往右靠的否则无法一次就进行恢复，因为这样子会导致恢复了局部逆序导致总体还不是正序的。究其本质原因是根据题目要求只会存在两个值被替换即存在a, b 使得b>a，b,..,a 而因为恰有两个值被替换也就是说其他值是顺序的即b与a中夹着的值均大于a, 若不大于a则a就不是那个被替换的值。也就是如果b与(b, a)序列中的任何一个交换都会导致a与被交换的值是逆序仍然要继续交换。
直观的理解我们交换值只是在中序遍历中随机抽两个不相同的点进行交换，那么设样例数据[1,2,3,4,5] 设被交换的点为2和4，交换之后为[1, 4, 3, 2, 5] 而因为4大于2，2大于1，所以交换之后4仍然大于1不会逆序但是4却大于3，同理2小于5，4也小于5，因此交换之后2与5无逆序但是2小于3，因此被交换的两值肯定分别对右边逆序和对左边逆序。

/**
 * Definition for a binary tree node.
 * 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 *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode *pre, *x, *y;
    void inOrder(TreeNode* node){
        if(node == nullptr){
            return;
        }
        inOrder(node->left);
        if(pre != nullptr && node->val < pre->val) {
            if(x == nullptr){
                x = pre;
                y = node;
            } else {
                y = node;
            }
        }
        pre = node;
        inOrder(node->right);
    }
    void recoverTree(TreeNode* root) {
        inOrder(root);
        int tmp = x->val;
        x->val = y->val;
        y->val = tmp;
    }
};