Recover Binary Search Tree

Two elements of a binary search tree (BST) are swapped by mistake.

Recover the tree without changing its structure.

 1 /** 2  * Definition for binary tree 3  * struct TreeNode { 4  *     int val; 5  *     TreeNode *left; 6  *     TreeNode *right; 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {} 8  * }; 9  */10 class Solution {11 public:12     void recoverTree(TreeNode *root) {13         vector<TreeNode *> nodes;14         dfs(root,nodes);15         int index1=-1;16         int index2=-1;17         for(int i=1;i<nodes.size();i++)18         {19             if(nodes[i]->val<nodes[i-1]->val)20             {21                 if(index1==-1) index1=i-1;22                 index2=i;23             }24         }25        26         int tmp=nodes[index1]->val;27         nodes[index1]->val=nodes[index2]->val;28         nodes[index2]->val=tmp;29         return;30        31     }     32    33     void dfs(TreeNode *root,vector<TreeNode *> &nodes)34     {35         if(root==NULL) return;36         dfs(root->left,nodes);37         nodes.push_back(root);38         dfs(root->right,nodes);39     }40 };

 1 /** 2  * Definition for binary tree 3  * struct TreeNode { 4  *     int val; 5  *     TreeNode *left; 6  *     TreeNode *right; 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {} 8  * }; 9  */10 class Solution {11 public:12     void recoverTree(TreeNode *root) {13     14         TreeNode *firstError=NULL;15         TreeNode *secondError=NULL;16         TreeNode *pre=NULL;17 18         19         dfs(root,pre,firstError,secondError);20         21         int tmp=firstError->val;22         firstError->val=secondError->val;23         secondError->val=tmp;24     }25     26     void dfs(TreeNode *root,TreeNode *&pre,TreeNode *&firstError,TreeNode *&secondError)27     {28         if(root==NULL) return;29         30         dfs(root->left,pre,firstError,secondError);31         32         if(pre!=NULL&&pre->val>root->val)33         {34             if(firstError==NULL) firstError=pre;35             secondError=root;36         }37         pre=root;38         39         dfs(root->right,pre,firstError,secondError);40     }41 };