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? > read more on how binary tree is serialized on OJ.

//Firstly, by inorder traversal, nodes are visited in ascending order.
//If two nodes are swapped, there must be two descent (two swapped nodes are not adjacent) or one descent (two swapped nodes are adjacent) step in inorder traversal.
//We use pointer 'pre' to record the last node we visited.  
//Normal Sequence 1 2 3 4 5 6 7 
//Swapped Sequence 1(adjacent) 1 2 4 3 5 6 7
//Swapped Sequence 2(inajacent) 1 2 6 4 5 3 7
//When we meet the first descent, say (6 4) in sequence 2, we let tmp1 points to node 6. (pre = 6, root = 4 now)
//When we meet the second descent, say (5 3) in sequence 2, we let tmp2 points to node 3. (pre = 5, root = 3)
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode * pre, * tmp1, * tmp2;
    void recoverTree(TreeNode* root) {
        pre = tmp1 = tmp2 = NULL;
        _recoverTree(root);
        int tmp = tmp1->val;
        tmp1->val = tmp2->val;
        tmp2->val = tmp;
    }
    void _recoverTree(TreeNode * root){
        if(root == NULL)
            return ;
        _recoverTree(root->left);
        
        if(pre == NULL){
            pre = root;
        }
        else{
            if(root->val < pre->val){
                //we need a swap
                if(tmp1 == NULL){
                    //first tmp
                    tmp1 = pre;
                    tmp2 = root;
                }
                else{
                    //second tmp
                    tmp2 = root;
                }
                
            }
        }
        pre = root;
        _recoverTree(root->right);
    }
};