# 恢复二叉搜索树
给你二叉搜索树的根节点 root ，该树中的两个节点被错误地交换。请在不改变其结构的情况下，恢复这棵树。
进阶：使用 O(n) 空间复杂度的解法很容易实现。你能想出一个只使用常数空间的解决方案吗？
示例 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
以下错误的选项是？
## aop
### before
```c
#include
using namespace std;
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) {}
};
```
### after
```c
```
## 答案
```c
class Solution
{
public:
TreeNode *pre = NULL;
TreeNode *one = NULL;
TreeNode *two = NULL;
bool search(TreeNode *root)
{
if (root == NULL)
return false;
if (search(root->left))
return true;
if (pre != NULL && pre->val > root->val)
{
if (one == NULL)
{
one = root;
two = pre;
}
else
{
two = root;
return true;
}
}
pre = root;
if (search(root->right))
return true;
return false;
}
void recoverTree(TreeNode *root)
{
search(root);
swap(one->val, two->val);
}
};
```
## 选项
### A
```c
class Solution
{
public:
TreeNode *x, *y, *pre;
void DFS(TreeNode *root)
{
if (root == nullptr)
return;
DFS(root->left);
if (pre && root->val < pre->val)
{
x = root;
if (!y)
y = pre;
else
return;
}
pre = root;
DFS(root->right);
}
void recoverTree(TreeNode *root)
{
DFS(root);
swap(x->val, y->val);
}
};
```
### B
```c
class Solution
{
public:
void insert(int val, vector &vals)
{
if (vals.size() > 0)
{
for (int i = 0; i < vals.size(); i++)
{
if (val < vals[i])
{
vals.insert(vals.begin() + i, val);
return;
}
}
}
vals.push_back(val);
}
void recoverTree(TreeNode *root)
{
stack s;
vector vals;
TreeNode *tem = root;
while (tem || !s.empty())
{
while (tem)
{
s.push(tem);
tem = tem->left;
}
if (!s.empty())
{
tem = s.top();
s.pop();
insert(tem->val, vals);
tem = tem->right;
}
}
tem = root;
int j = 0;
while (tem || !s.empty())
{
while (tem)
{
s.push(tem);
tem = tem->left;
}
if (!s.empty())
{
tem = s.top();
s.pop();
tem->val = vals[j++];
tem = tem->right;
}
}
}
};
```
### C
```c
class Solution
{
public:
vector order;
void inOrder(TreeNode *root)
{
if (root->left)
inOrder(root->left);
order.push_back(root);
if (root->right)
inOrder(root->right);
}
void recoverTree(TreeNode *root)
{
inOrder(root);
int left = -1, right = -1;
for (int i = 0; i < order.size() - 1; ++i)
{
if (order[i]->val > order[i + 1]->val)
{
if (left == -1)
left = i;
right = i + 1;
}
}
if (right == -1)
swap(order[left]->val, order[left + 1]->val);
else
swap(order[left]->val, order[right]->val);
}
};
```