Recover Binary Search Tree (A solution using O(n) space )

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?

1. Recursive inorder traversal

a. 开始没想清楚怎么把那两个错误的node找出来
b. 应该用*& 的地方用了*。 后来发现不作为param来pass还更简单。

Writing this would work, *&      void helper(TreeNode *cur, TreeNode *&first, TreeNode *&second, TreeNode *&pre)    {        if (cur==NULL)            return;                   helper(cur->left, first, second, pre);        if (pre)        {          if (pre->val>cur->val)           {             if (first==NULL)              {                   first = pre;                   second = cur;              }             else                  second = cur;                     }        }          pre = cur;        helper(cur->right, first, second, pre);    }     void recoverTree(TreeNode *root) {         if (root==NULL||(root->left==NULL && root->right==NULL))         {             return;         }                 vector<TreeNode *> t;         TreeNode *first=NULL, *second=NULL, *pre=NULL;         helper(root,first, second, pre);           int tmp = first->val;         first->val = second->val;         second->val = tmp;               }

Not working, as the TreeNode * remains NULL Runtime Error!      void helper(TreeNode *cur, TreeNode *first, TreeNode *second, TreeNode *pre)    {        if (cur==NULL)            return;                   helper(cur->left, first, second, pre);        if (pre)        {        if (pre->val>cur->val)           {             if (first==NULL)              {                   first = pre;                   second = cur;              }             else                  second = cur;                     }        }        pre = cur;        helper(cur->right, first, second, pre);    }     void recoverTree(TreeNode *root) {         if (root==NULL||(root->left==NULL && root->right==NULL))         {             return;         }                 vector<TreeNode *> t;         TreeNode *first=NULL, *second=NULL, *pre=NULL;         helper(root,first, second, pre);           int tmp = first->val;         first->val = second->val;         second->val = tmp;               }

Then, after some research, writing those * out like the following produces much cleaner code and less head scratch about *&!!!     class Solution { public:     TreeNode *first, *second,  *pre;    void helper(TreeNode *cur)    {        if (cur==NULL)            return;                   helper(cur->left);        if (pre)        {          if (pre->val>cur->val)           {             if (first==NULL)              {                   first = pre;                   second = cur;              }             else                  second = cur;                     }           pre = cur;        }        else        pre = cur;        helper(cur->right);    }     void recoverTree(TreeNode *root) {         if (root==NULL||(root->left==NULL && root->right==NULL))         {             return;         }                 vector<TreeNode *> t;         first=NULL, second=NULL, pre=NULL;         helper(root);           int tmp = first->val;         first->val = second->val;         second->val = tmp;               } };