Leetcode99 恢复二叉搜索树

题目地址：
https://leetcode-cn.com/problems/recover-binary-search-tree/

【思路】
在一次遍历的过程中，找到两个异常的节点，把这两个节点的值交换。
怎么找呢？
二叉搜索树的中序遍历是一个升序数组
可记录每一次遍历的前置节点
遍历到的节点的value一定要比前置节点的大
如果比前置节点要小 则记录为异常

上代码

class Solution {
public:
    TreeNode* x = nullptr;
    TreeNode* y = nullptr;
    TreeNode* preValue = nullptr;
    void inOrder(TreeNode* node){
        if(node == nullptr) return;
        inOrder(node -> left);
        if(preValue != nullptr){
            if(node -> val < preValue -> val){
                y = node;
                if(x == nullptr) x = preValue;
                else return;
//记录节点的小技巧
            }
        }
        preValue = node;
        inOrder(node ->right);
    }
    void recoverTree(TreeNode* root) {
        inOrder(root);
        int tmp = x->val;
        x->val = y->val;
        y->val = tmp;
    }

};

【记录节点的小技巧】
有两种交换情况：
相邻的两个节点交换了，不相邻的两个节点交换了

image.png

相邻交换记录异常的两个就行了
不相邻交换时，异常的preValue才是出问题的那个
（自己想一想）