# 恢复二叉搜索树

<p>给你二叉搜索树的根节点 <code>root</code> ，该树中的两个节点被<span style="color:red">错误</span>地交换。请在不改变其结构的情况下，恢复这棵树。</p><p><strong>进阶：</strong>使用 O(<em>n</em>) 空间复杂度的解法很容易实现。你能想出一个只使用常数空间的解决方案吗？</p><p><strong>示例 1：</strong></p><img alt="" src="https://img-blog.csdnimg.cn/img_convert/ec4e4b2849cccb75be04428664afb2fc.png#pic_center" /><pre><strong>输入：</strong>root = [1,3,null,null,2]<strong><br />输出：</strong>[3,1,null,null,2]<strong><br />解释：</strong>3 不能是 1 左孩子，因为 3 > 1 。交换 1 和 3 使二叉搜索树有效。</pre><p><strong>示例 2：</strong></p><img alt="" src="https://img-blog.csdnimg.cn/img_convert/c039bf633cb8b3bfbb70a26e931a4f53.png#pic_center" /><pre><strong>输入：</strong>root = [3,1,4,null,null,2]<strong><br />输出：</strong>[2,1,4,null,null,3]<strong><br />解释：</strong>2 不能在 3 的右子树中，因为 2 < 3 。交换 2 和 3 使二叉搜索树有效。</pre><p><strong>提示：</strong></p><ul>	<li>树上节点的数目在范围 <code>[2, 1000]</code> 内</li>	<li><code>-2<sup>31</sup> <= Node.val <= 2<sup>31</sup> - 1</code></li></ul>
<p>以下<span style="color:red">错误</span>的选项是？</p>

## aop

### before

```c
#include <bits/stdc++.h>
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<int> &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<TreeNode *> s;
        vector<int> 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<TreeNode *> 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);
    }
};
```