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?

Solution: 1. recursive solution. O(n) space. get inorder list first.
2. recursive solution. O(n) space. with only auxiliary two pointers.
3. Morris inorder traversal. O(1) space. with only auxiliary two pointers.

 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 };