Recover Binary Search Tree

给一个bst, 里面有两个node互换了. 找出并且换回. 因为是bst, 所以要利用bst的性质找两个node.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    TreeNode first = null;
    TreeNode second = null;
    TreeNode last = new TreeNode(Integer.MIN_VALUE);
    public void recoverTree(TreeNode root) {
        if(root == null)
            return;
        rec(root);
        int tmp = first.val;
        first.val = second.val;
        second.val = tmp;
    }
    public void rec(TreeNode root) {
        if(root == null)
            return;
        rec(root.left);
        if(first == null && last.val > root.val)
            first = last;
        if(first != null && last.val > root.val)
            second = root;
        last = root;
        rec(root.right);
    }
}