二叉搜索树中的两个节点被错误地交换。
请在不改变其结构的情况下，恢复这棵树。
示例 1:
输入: [1,3,null,null,2]
1
/
3
\
2
输出: [3,1,null,null,2]
3
/
1
\
2
示例 2:
输入: [3,1,4,null,null,2]
3
/ \
1 4
/
2
输出: [2,1,4,null,null,3]
2
/ \
1 4
/
3
思路：
首先，要知道二叉搜索树的中序遍历必然是从小到大排列的，所以一种做法是拿出一个数组去存储这些数据，然后判断哪两个点出现逆序。另一种做法则是中序遍历过程中完成这个判断过程，用pre指针指向前一个指针，root指针指向当前指针，n1指针指向前一个逆序结果，n2指针指向后一个逆序结果。具体实现如下。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
void recoverTree(TreeNode* root) {
n1=n2=pre=nullptr;
recoverTreeCore(root);
if(n1 && n2)
{
swap(n1->val,n2->val);
}
}
void recoverTreeCore(TreeNode* root)
{
if(!root)
{
return;
}
recoverTreeCore(root->left);
if(pre)
{
if(root->val<pre->val)
{
if(!n1)
{
n1=pre;
}
n2=root;
}
}
pre=root;
recoverTreeCore(root->right);
}
TreeNode *n1,*n2,*pre;
};
