144. 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?
Binary Search Tree has a property that in-order traversal generates a non-decreasing array. So the easiest solution is to do an in-order traversal and find which are the two values being swapped. Doing this we need an array of O(n).
I overcome this by using recursion. When we are in the traversal process we can maintain a variable which has the value of the previous node and when the current node is smaller than the previous one we mark it down. In the end we should have at least one pair of incorrect nodes. Swap it and return.
You can read my code here
https://gist.github.com/zyzyis/6c8a2a44707cf61cad74
PS: Recursion is not an O(1) space complexity approach. It should be O(logn) and O(n) for worst case. I found from internet that using threaded binary tree which can lead to O(1) space complexity, will updated later.