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

/**
 * 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 inOrder(TreeNode *&pre,TreeNode *&mis1,TreeNode *&mis2, TreeNode *root)
{
    if(root==NULL)return;
    inOrder(pre,mis1,mis2,root->left);
    if(pre!=NULL&&pre->val>root->val)
    {
        if(mis1==NULL)
        {
            mis1=pre;
            mis2=root;
        }
        else
        {
            mis2=root;
        }
    }
    pre=root;
    inOrder(pre,mis1,mis2,root->right);
}
void recoverTree(TreeNode *root) 
{
    TreeNode *pre=NULL, *mis1=NULL, *mis2=NULL;
    inOrder(pre,mis1,mis2,root);
    if(mis1&&mis2)
    {
        int tmp=mis1->val;
        mis1->val=mis2->val;
        mis2->val=tmp;
    }
}
/*
private:
   TreeNode *pre=NULL, *mis1=NULL, *mis2=NULL;
public:
void inOrder(TreeNode *root)
{
    if(root==NULL)return;
    inOrder(root->left);
    if(pre!=NULL&&pre->val>root->val)
    {
        if(mis1==NULL)
        {
            mis1=pre;
            mis2=root;
        }
        else
        {
            mis2=root;
        }
    }
    pre=root;
    inOrder(root->right);
}
    void recoverTree(TreeNode *root) {
        inOrder(root);
        if(mis1&&mis2)
        {
            int tmp=mis1->val;
            mis1->val=mis2->val;
            mis2->val=tmp;
        }
    }
*/
};