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?

confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.

Analyse: Traverse the binary tree inorderly, then find the two wrong numbers and swap them.

1. Recursion

Runtime: 56ms.

 1 /**
 2  * Definition for a binary tree node.
 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* > store; //store the nodes visited by indorder traversal
14         if(!root || (!root->left && !root->right)) return;
15         inorder(root, store);
16         
17         int left = 0, right = store.size() - 1;
18         for(int i = 0; i < store.size(); i++){
19             if(store[i + 1]->val < store[i]->val){
20                 left = i;
21                 break;
22             }
23         }
24         for(int j = store.size() - 1; j >= 0; j--){
25             if(store[j]->val < store[j - 1]->val) {
26                 right = j;
27                 break;
28             }
29         }
30         swap(store[left]->val, store[right]->val);
31         return ;
32     }
33     void inorder(TreeNode* root, vector<TreeNode* > &store){
34         if(!root) return;
35         
36         inorder(root->left, store);
37         store.push_back(root);
38         inorder(root->right, store);
39     }
40 };

2. Iteration

Runtime: 56ms.

 1 /**
 2  * Definition for a binary tree node.
 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* > store; //store the nodes visited by indorder traversal
14         if(!root || (!root->left && !root->right)) return;
15         TreeNode* current = root;
16         stack<TreeNode* > stk;
17         
18         while(!stk.empty() || current){
19             if(current){
20                 stk.push(current);
21                 current = current->left;
22             }
23             else{
24                 current = stk.top();
25                 stk.pop();
26                 store.push_back(current);
27                 current = current->right;
28             }
29         }
30         
31         int left = 0, right = store.size() - 1;
32         for(int i = 0; i < store.size(); i++){
33             if(store[i + 1]->val < store[i]->val){
34                 left = i;
35                 break;
36             }
37         }
38         for(int j = store.size() - 1; j >= 0; j--){
39             if(store[j]->val < store[j - 1]->val) {
40                 right = j;
41                 break;
42             }
43         }
44         swap(store[left]->val, store[right]->val);
45         return ;
46     }
47 };