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?

两个node互换。举个例子，tree inorder：1，2，3，4，5，6，7

有可能会有1对降序：1，2，4，3，5，6，7。也有可能会有两对降序：1，6，3，4，5，2，7

但是无论如何，第一次降序的大的和最后一次降序小的就是对调的两个。

public class Solution {
    //Time: O(n)
    private TreeNode first = null;
    private TreeNode second = null;
    private TreeNode last = null;
    private void find(TreeNode root) {
        if (root == null) {
            return;
        }
        
        find(root.left);
        if (last != null && first == null && last.val > root.val) {
            first = last;
        }
        if (last != null && first != null && last.val > root.val) {
            second = root;
        }
        last = root;
        find(root.right);
    }
    
    public void recoverTree(TreeNode root) {
        find(root);
        int temp = first.val;
        first.val = second.val;
        second.val = temp;
    }
}