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?

[Thoughts]:
设三个指针， pre，first 和second。
pre按inorder顺序遍历一遍，因为BST的inorder序列肯定是有序的， pre一定<=current。 若不是则就是错误节点。
swap first和second的值。

public class Solution {
    TreeNode pre = null, first = null, second = null;
    public void recoverTree(TreeNode root) {
        if(root==null) return;
        inOrder(root);
        
        int temp = first.val;
        first.val = second.val;
        second.val = temp;
        
    }
    public void inOrder(TreeNode root){
        if(root==null) return;
        inOrder(root.left);
        if(pre!=null && pre.val>root.val){
            if(first==null)
                first = pre;
            second = root;//note:first只更新一次，更新first时，我们找到的second有可能不是错误点，也有可能是。 
        }
        pre = root;
        inOrder(root.right);
    }
}