EEPW论坛

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.

The serialization of a binary tree follows a level order traversal, where '#' signifies a path terminator where no node exists below.

Here's an example:

   1
  / \
 2   3
    /
   4
    \
     5

1. class Solution  

2. {  

3. public:  

4.     void recoverTree(TreeNode* root)  

5.     {  

6.         TreeNode* pre = NULL;  

7.         TreeNode* first = NULL;  

8.         TreeNode* second = NULL;  

9.   

10.         inorder(root, pre, first, second);  

11.         if (first!=NULL)  

12.         {  

13.             if (second==NULL)  

14.             {  

15.                 second = pre;  

16.             }  

17.   

18.             int tmp = first->val;  

19.             first->val = second->val;  

20.             second->val = tmp;  

21.         }  

22.     }  

23.   

24.     void inorder(TreeNode* root, TreeNode* &pre,   

25.                         TreeNode* &first, TreeNode* & second)  

26.     {  

27.         if (root==NULL)  

28.         {  

29.             return;  

30.         }  

31.   

32.         if (root->left)  

33.         {  

34.             inorder(root->left, pre, first, second);  

35.         }  

36.   

37.         if (pre!=NULL)  

38.         {  

39.             if (first==NULL && root->val<pre->val)  

40.             {  

41.                 first = pre;  

42.             }  

43.             else if (first && root->val>=first->val)  

44.             {  

45.                 second = pre;  

46.                 return;  

47.             }  

48.         }  

49.   

50.         pre = root;  

51.         if (root->right)  

52.         {  

53.             inorder(root->right, pre, first, second);  

54.         }  

55.     }  

56. };