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?

 /**

  * 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 recoverTree(TreeNode *root) {

         vector<TreeNode *> nodes;

         dfs(root,nodes);

         int index1=-;

         int index2=-;

         for(int i=;i<nodes.size();i++)

         {

             if(nodes[i]->val<nodes[i-]->val)

             {

                 if(index1==-) index1=i-;

                 index2=i;

             }

         }

         int tmp=nodes[index1]->val;

         nodes[index1]->val=nodes[index2]->val;

         nodes[index2]->val=tmp;

         return;

     }     

     void dfs(TreeNode *root,vector<TreeNode *> &nodes)

     {

         if(root==NULL) return;

         dfs(root->left,nodes);

         nodes.push_back(root);

         dfs(root->right,nodes);

     }

 };

 /**

  * 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 recoverTree(TreeNode *root) {

         TreeNode *firstError=NULL;

         TreeNode *secondError=NULL;

         TreeNode *pre=NULL;

         dfs(root,pre,firstError,secondError);

         int tmp=firstError->val;

         firstError->val=secondError->val;

         secondError->val=tmp;

     }

     void dfs(TreeNode *root,TreeNode *&pre,TreeNode *&firstError,TreeNode *&secondError)

     {

         if(root==NULL) return;

         dfs(root->left,pre,firstError,secondError);

         if(pre!=NULL&&pre->val>root->val)

         {

             if(firstError==NULL) firstError=pre;

             secondError=root;

         }

         pre=root;

         dfs(root->right,pre,firstError,secondError);

     }

 };