public class _99 {
    static class Solution {
        TreeNode first;
        TreeNode last;
        TreeNode pre;

        public void recoverTree(TreeNode root) {
            inOrder(root);
            int temp = first.val;
            first.val = last.val;
            last.val = temp;
        }

        public void inOrder(TreeNode root) {
            if (root == null) return;
            inOrder(root.left);
            if (pre != null && root.val < pre.val) {
                first = first == null ? pre : first;
                last = root;
            }
            pre = root;
            inOrder(root.right);
        }
    }
}