LeetCode Problem : Recover Binary Search Tree

Problem

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.


OJ's Binary Tree Serialization:
The serialization of a binary tree follows a level order traversal, where '#' signifies a path terminator where no node exists below.

Here's an example:
   1
  / \
 2   3
    /
   4
    \
     5
The above binary tree is serialized as "{1,2,3,#,#,4,#,#,5}".

Code

void rt_inOrder(TreeNode *node,TreeNode **l,TreeNode **n1,TreeNode **n2){
    if(!node)
        return;
    rt_inOrder(node->left,l,n1,n2);
    if(*l && (*l)->val > node->val){
        if(!(*n1)){
            *n1 = *l;
            *n2 = node;
        }
        else{
            *n2 = node;
        }
    }
    *l = node;
    rt_inOrder(node->right,l,n1,n2);
}

void recoverTree(TreeNode *root) {
    // IMPORTANT: Please reset any member data you declared, as
    // the same Solution instance will be reused for each test case.
    TreeNode *l = 0,*n1 = 0,*n2 = 0;
    rt_inOrder(root,&l,&n1,&n2);
    swap(n1->val,n2->val);
}