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 24 35 6 7 //Swapped Sequence 2(inajacent) 1 264 537 //When we meet the first descent, say (6 4) in sequence 2, we lettmp1points to node 6. (pre = 6, root = 4 now) //When we meet the second descent, say (5 3) in sequence 2, we lettmp2points 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); } };