Recover Binary Search Tree [Leetcode]

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}".

Solution: we solve this problem by doing In-order traversal. Assume the In-order traversal of a given tree without two swapped nodes by mistake is 1, 2, 3, 4, 5, 5, 6, 6, 6, 7, 7, 7, 8, 9. We has three probabilities:

1. If there is no two swapped nodes by mistake, there is no inversions; 
2. If a node with value a is swapped with the next first node with value b>a in the In-order traversal (e.g. the first 5 and the first 6), we get one inversion; 
3. Otherwise we get two inversion (e.g. the first 5 and the first 7). 

For case 1, we do not need to anything; For case 2, we simply exchange the values of two nodes involving in the inversion; For case 3, we need to exchange the first node in the first inversion and the second node in the second inversion. We note that the pointer pre is used to track the last visited node before the current node.

/**
 * 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 recoverTreeHelper(TreeNode *root, TreeNode* &pre, TreeNode* &fst, TreeNode* &snd){
        if(!root) return;
        recoverTreeHelper(root->left, pre, fst, snd);
        if(pre!=NULL && pre->val>root->val){
            if(fst==NULL){
                fst=pre;
                snd=root;
            }
            else
                snd=root;
        }
        pre=root;
        recoverTreeHelper(root->right, pre, fst, snd);
    }
    void recoverTree(TreeNode *root) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        TreeNode *fst=NULL;
        TreeNode *snd=NULL;
        TreeNode *pre=NULL;
        recoverTreeHelper(root, pre, fst, snd);
        if(fst==NULL)
            return;
        int tmp = fst->val;
        fst->val = snd->val;
        snd->val = tmp;
    }
};