题目地址：
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才是出问题的那个
（自己想一想）
