LeetCode: 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?

Solution One

Key Point: 1. the sequence of values should be in the ascending order with in-order traversal
2. The previous node should be held
3. It's not really O(1) space since the recursion stack needs O(n) extra space

Solution Two

I implemented it in Java with O(N) space. Using two ArrayLists to hold the sequence of nodes and values.