# [leetcode] RecoverBinary 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.

```//Firstly, by inorder traversal, nodes are visited in ascending order.
//If two nodes are swapped, there must be two descent (two swapped nodes are not adjacent) or one descent (two swapped nodes are adjacent) step in inorder traversal.
//We use pointer 'pre' to record the last node we visited.
//Normal Sequence 1 2 3 4 5 6 7
//Swapped Sequence 1(adjacent) 1 2 4 3 5 6 7
//Swapped Sequence 2(inajacent) 1 2 6 4 5 3 7
//When we meet the first descent, say (6 4) in sequence 2, we let tmp1 points to node 6. (pre = 6, root = 4 now)
//When we meet the second descent, say (5 3) in sequence 2, we let tmp2 points to node 3. (pre = 5, root = 3)
/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode * pre, * tmp1, * tmp2;
void recoverTree(TreeNode* root) {
pre = tmp1 = tmp2 = NULL;
_recoverTree(root);
int tmp = tmp1->val;
tmp1->val = tmp2->val;
tmp2->val = tmp;
}
void _recoverTree(TreeNode * root){
if(root == NULL)
return ;
_recoverTree(root->left);

if(pre == NULL){
pre = root;
}
else{
if(root->val < pre->val){
//we need a swap
if(tmp1 == NULL){
//first tmp
tmp1 = pre;
tmp2 = root;
}
else{
//second tmp
tmp2 = root;
}

}
}
pre = root;
_recoverTree(root->right);
}
};

``` This site uses Akismet to reduce spam. Learn how your comment data is processed.