Recover Binary Search Tree

 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         TreeNode* prev = NULL;
14         TreeNode* first = NULL;
15         TreeNode* second = NULL;
16         recoverTreeRe(root, prev, first, second);
17         swap(first->val, second->val);
18     }
19     
20     void recoverTreeRe(TreeNode* root, TreeNode* &prev, TreeNode* &first, TreeNode* &second)
21     {
22         if(!root) return;
23         recoverTreeRe(root->left, prev, first, second);
24         if(prev && prev->val > root->val) {
25             if(!first) {
26                 first = prev;
27             }
28             second = root;
29         }
30         prev = root;
31         recoverTreeRe(root->right, prev, first, second);
32     }
33 };