题目意思为一个二叉搜索树，有两个元素位置颠倒了，现在让你把它还原，但是题目要求空间复杂度O(1)，我们知道二叉搜索树的中序遍历是有序的，那么利用这一点，找到第一个无序的

地方，记录为first,第二个为second，这样就是常量空间复杂度了，注意有一种情况是刚好两个相邻的颠倒顺序。

/** * Definition for binary tree * struct TreeNode { *     int val; *     TreeNode *left; *     TreeNode *right; *     TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {private: TreeNode *pre;         TreeNode *first;         TreeNode *second;public:    void recoverTree(TreeNode *root) {        // Start typing your C/C++ solution below        // DO NOT write int main() function        if(root==NULL)        return;        pre = NULL;        first = NULL;        second = NULL;        Inorder(root);        first->val ^= second->val;        second->val ^= first->val;        first->val ^= second->val;    }    void Inorder(TreeNode *root)    {        if(root==NULL)        return;        Inorder(root->left);        if(pre!=NULL)        {            if(pre->val > root->val)            {                if(first==NULL)                {                    first = pre;                    second = root;                }                else                {                    second = root;                }            }        }        pre = root;        Inorder(root->right);    }};