Leetcode---Recover Binary Search Tree

Two elements of a binary search tree (BST) are swapped by mistake.

Recover the tree without changing its structure.

Note:
A solution using O(n) space is pretty straight forward. Could you devise a constant space solution?

confused what "{1,#,2,3}" means? 

Show Tags

Have you met this question in a real interview?

二叉排序树，中序遍历的时候应该输出一个有序序列。但是当反转的时候，就会出现当前节点小于前一节点的情况。记录第一个反转的节点和最后一个反转的节点，然后简单的互换节点内容即可，而无需互换节点本身。

TreeNode * pre=NULL;
TreeNode * p1=NULL;
TreeNode * p2=NULL;
void recoverTreeHelper(TreeNode *root) {
    if(root==NULL)
        return;
    recoverTreeHelper(root->left);
    if(pre==NULL)
        pre=root;
    else{
        if(root->val<pre->val){
            if(p1==NULL)
                p1=pre;
            p2=root;
        }
        pre=root;
    }
    recoverTreeHelper(root->right);
}
void recoverTree(TreeNode *root) {
    recoverTreeHelper(root);
    if(p1!=NULL && p2!=NULL)
        swap(p1->val,p2->val);
}