Recover Binary Search Tree
Desicription
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?
Solution
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
 class Solution { private: TreeNode* pre = new TreeNode(INT_MIN); TreeNode* first = NULL; TreeNode* second = NULL; void searchTree(TreeNode* root) { if(!root) return ; searchTree(root>left); if(!first && pre>val >= root>val) first = pre; if(first && pre>val >= root>val) second = root; pre = root; searchTree(root>right); } public: void recoverTree(TreeNode* root) { searchTree(root); swap(first>val, second>val); } };
