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?

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

/**

 * Definition for binary tree

 * public class TreeNode {

 *     int val;

 *     TreeNode left;

 *     TreeNode right;

 *     TreeNode(int x) { val = x; }

 * }

 */

public class Solution {

    

    TreeNode first;

    TreeNode second;

    TreeNode pre;

    int status;

    

    public void recoverTree(TreeNode root) {

        first = null;

        second = null;

        pre = null;

        status = 0;

        check(root);

        int tmp = first.val;

        first.val = second.val;

        second.val = tmp;

    }

    

    private void check(TreeNode node) {

        if(node==null || status==2) {

            return;

        }

        check(node.left);

        if(pre!=null && status==0 && pre.val>node.val) {

            status = 1;

            first = pre;

            second = node;

        } else if(pre!=null && status==1 && pre.val>node.val) {

            status = 2;

            second = node;

        }

        pre = node;

        check(node.right);

    }

}

=======

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
   
    private TreeNode pre;
    private TreeNode first = null;
    private TreeNode second = null;
    public void recoverTree(TreeNode root) {
        visit(root);
        int tmp = first.val;
        first.val = second.val;
        second.val = tmp;
    }
   
    private void visit(TreeNode node) {
        if (node == null) {
            return;
        }
        visit(node.left);
        if (pre != null) {
            if (pre.val > node.val) {
                if (first == null) {
                    first = pre;
                    second = node;
                } else {
                    second = node;
                   return;
                }
            }
        }
        pre = node;
        visit(node.right);
    }
}