题解 | #恢复二叉搜索树#

 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    void recoverTree(TreeNode *root) {
        //一种朴素的想法就是用前序遍历把树里的元素存入vector，排序好后再填回去
        //但这样空间复杂度就是O(n)，可以进行优化：正常情况下，通过前序遍历得到的
        //序列是递增的，因此如果发现了在某个位置的数字比前一个小，那么说明这两个
        //数字中有一个被调换了，因此这两个数都先被默认为可能存在“错误”，存入一个
        //vector中。这样的位置在整个前序遍历序列中应该存在两个，全部找到后就可以
        //根据这四个数的大小情况来判断哪两个数被调换了。
        visit(root);
        sort(vcval.begin(), vcval.end());
        for(int i=0;i<vcval.size();i++)
        {
            vcnode[i]->val=vcval[i];
        }
    }
    void visit(TreeNode*root)
    {
        if(root==nullptr||cnt==2)
            return;
        visit(root->left);
        if(root->val<lastval)//找到了一个错误点
        {
            vcnode.push_back(lastnode);
            vcnode.push_back(root);
            vcval.push_back(lastval);
            vcval.push_back(root->val);
            cnt++;
        }
        lastval=root->val;//将当前结点的值作为lastval，用于下一次比较
        lastnode=root;
        visit(root->right);
    }
private:
    int lastval=-9999999;//用于保存上一个结点值
    TreeNode* lastnode=nullptr;//用于保存上一个结点指针
    vector<int> vcval;//用于保存所有可能的错误值
    vector<TreeNode*> vcnode;//用于保存所有可能的错误点
    int cnt=0;//用于记录找到了几组错误点(一共有两组),如果都找到了可以停止遍历
};