99 Recover Binary Search Tree
Two elements of a binary search tree (BST) are swapped by mistake.
Recover the tree without changing its structure.
A solution using O(n) space is pretty straight forward. Could you devise a constant space solution?
Three pointers are needed, first and second respectively represent the first and second disordered nodes, and pre points to the previous node of the current node’s in-order traversal.
The traditional in-order traversal recursion is used here, but where the node value should be output, it is replaced by judging the size of pre and the current node value. If pre is larger, if first is empty, first point to the node pointed to by pre, or else, set second to the current node.
In this way, the in-order traverses the entire tree, and if both first and second exist, then their node values can be exchanged. The space complexity of this algorithm is still O(n), where n is the height of the tree.