[LeetCode] 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?

这题用O(n)的辅助空间比较好做，中序遍历后排个序O(nlogn)。但要不改变树的结构来完成就比较难了。

我只能想到一个把bst转为double link list后排序，再转为bst的方法，但转为bst就没法保证依然是原来bst的结构了。

 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 private:
12     vector<int> val;
13     vector<TreeNode* > index;
14 public:
15     void traverse(TreeNode *node)
16     {
17         if (node == NULL)
18             return;
19             
20         traverse(node->left);
21         val.push_back(node->val);
22         index.push_back(node);
23         traverse(node->right);
24     }
25     
26     void recoverTree(TreeNode *root) {
27         // Start typing your C/C++ solution below
28         // DO NOT write int main() function
29         traverse(root);
30         sort(val.begin(), val.end());
31         for(int i = 0; i < val.size(); i++)
32             index[i]->val = val[i];
33     }
34 };

空间O(1)

 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 treeWalk(TreeNode* root, TreeNode*& prv, TreeNode*& first, TreeNode*& second)
13     {
14       if(root==NULL)
15          return;
16       treeWalk(root->left,prv,first,second);
17       if((prv!=NULL)&&(prv->val>root->val)){
18           if(first==NULL)
19              first=prv;
20            second=root;
21       }
22       prv=root;
23       treeWalk(root->right,prv,first,second);
24     }
25   
26     void recoverTree(TreeNode *root) {
27         // Start typing your C/C++ solution below
28         // DO NOT write int main() function
29         TreeNode* first=NULL;
30         TreeNode* second=NULL;
31         TreeNode* prv=NULL;
32         treeWalk(root,prv,first,second);
33         int tmp=first->val;
34         first->val=second->val;
35         second->val=tmp;
36     }
37 };

空间O(1)

 1 class Solution {
 2 public:
 3     void treeWalk(TreeNode* root, TreeNode*& prv, TreeNode*& first, TreeNode*& second)
 4     {
 5       if(root==NULL)
 6          return;
 7       treeWalk(root->left,prv,first,second);
 8       if((prv!=NULL)&&(prv->val>root->val)){
 9           if(first==NULL)
10              first=prv;
11            second=root;
12       }
13       prv=root;
14       treeWalk(root->right,prv,first,second);
15     }
16  
17     void recoverTree(TreeNode *root) {
18         // Start typing your C/C++ solution below
19         // DO NOT write int main() function
20         TreeNode* first=NULL;
21         TreeNode* second=NULL;
22         TreeNode* prv=NULL;
23         treeWalk(root,prv,first,second);
24         int tmp=first->val;
25         first->val=second->val;
26         second->val=tmp;
27     }
28 };