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?
We can use a stack to do an in order traverse of the tree, as it can produce a sorted list of a binary search tree. In the process, we keep track of two pointers pre, cur:
If we encounter pre.val > cur.val the first time, we get the first error node p1 = pre,
Tree traversal is often implemented using Stack or Recursion. In this case, the space complexity is O(h), where h is the height of the tree. We describe a method based on Morris Traversal for tree traversal using O(1) space.
The basic idea of Morris Traversal is that: For current Node Cur, we use the right most leaf of its left child to record the location of Cur.
preOfCur = getRightMost(Cur.left)
preOfCur.right = Cur
Suppose we start from root, after running
preOfRoot = getRightMost(root.left)
preOfRoot.right = root
preOfRoot’s right child will point to root. Now we can traverse the left branch of the tree.