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?

二叉排序树中有两个节点被交换了，要求把树恢复成二叉排序树。


中序遍历二叉树生成序列，然后对序列中排序错误的进行调整。最后再进行一次赋值操作。

递归中序遍历二叉树，设置一个pre指针，记录当前节点中序遍历时的前节点，如果当前节点大于pre节点的值，说明需要调整次序。
if(pre!=null&&pre.val>root.val)

这个其实将中序遍历序列看成线性递增序列，在调换位置后，遍历第一次出现大小有问题的第一个位置后最后一个出现有问题的要替换
如1 4 5  6 7 8 9
换后 1 7 5 6 4 8 9
于是代码中
if(mistake1==null){
mistake1=pre;
mistake2=root;
}
else{
mistake2=root;
}
}

完整代码：
TreeNode pre;
TreeNode mistake1;
TreeNode mistake2;
      public void recoverTree(TreeNode root) {
        r_traversal(root);
        if(mistake1!=null&&mistake2!=null){
        int temp=mistake1.val;
        mistake1.val=mistake2.val;
        mistake2.val=temp;
        }
    }
private void r_traversal(TreeNode root) {
// TODO 自动生成的方法存根
if(root==null)
return;
if(root.left!=null)
r_traversal(root.left);
if(pre!=null&&pre.val>root.val){
if(mistake1==null){
mistake1=pre;
mistake2=root;
}
else{
mistake2=root;
}
}
pre=root;
if(root.right!=null){
r_traversal(root.right);
}
}