学步园

题目：

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.

思路：

该题非常简单，仅仅需要想明白如何发现这两个错换了的元素以及怎么判断就是这两个。

知道了这两个之后，分别记下他们的地址（引用），直接交换两个值即可。

首先，我们都知道，BST在中序遍历的时候一定是有序的。因此，以终须遍历，遇到第一个val小于前一个val的时候，前一个一定就是第一个错换的元素。

继续往后，再一次遇到前一个的val大于当前val的时候，当前val一定是第二个元素。

结束，完成交换即可，如此简单。

AC代码：

public class Recover_Binary_Search_Tree {
    TreeNode first = null;
    TreeNode second = null;
    TreeNode pre = new TreeNode(Integer.MIN_VALUE);

    private void recoverByInterOrder(TreeNode root){
        if(root==null)
            return;
        recoverByInterOrder(root.left);
        if(first==null && pre.val>=root.val){
            first = pre;
        }
        if(first!=null && pre.val>=root.val){
            second = root;
        }

        pre = root;

        recoverByInterOrder(root.right);

    }
    public void recoverTree(TreeNode root) {
        recoverByInterOrder(root);
        int val = first.val;
        first.val = second.val;
        second.val = val;
    }
}