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?

confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.

Solution:

// O(n): traverse->sort->reassign to all
/**

 
public class Solution {
    // TreeNode needs to do backtrace, so we cannot pass them as parameters.
    TreeNode prev = null;
    TreeNode first = null;
    TreeNode second = null;
    public void recoverTree(TreeNode root) {
        
        inOrderTreverse(root);
        
        // swap value
        int tmp = first.val;
        first.val = second.val;
        second.val = tmp;
    }
    public void inOrderTreverse(TreeNode root){
        if(root == null) 
            return;
            
        inOrderTreverse(root.left);
        
        if(prev != null && prev.val > root.val){
            if(first == null)
                first = prev;
            second = root;
        }
        prev = root;
        
        inOrderTreverse(root.right);
    }
}