[Leetcode] 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?
如果使用O(n)的空间来做的话比较简单，用一个链表来存储树的中序遍历的结果，因为BST的中序遍历应该是一个递增的序列，那么再扫一遍这个链表找到两个错位的节点就可以了。但是如果使用O(1)的空间做，那么就需要搬出Morris遍历了，在遍历的过程中比较当前节点和前一节点的大小关系来进行判断。

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public void recoverTree(TreeNode root) {
        TreeNode node1 = null, node2 = null, pre = null;
        TreeNode cur = root, tmp;
        while(cur != null) {
            if(cur.left == null) {
                if(pre != null) {
                    if(cur.val < pre.val) {
                        if(node1 == null) 
                            node1 = pre;
                        node2 = cur;
                    }
                }
                pre = cur;
                cur = cur.right;
            }
            else {
                tmp = cur.left;
                while(tmp.right != null && tmp.right != cur) tmp = tmp.right;
                if(tmp.right == null) {
                    tmp.right = cur;
                    cur = cur.left;
                }
                else {
                    if(pre != null) {
                        if(cur.val < pre.val) {
                            if(node1 == null) 
                                node1 = pre;
                            node2 = cur;
                        }
                    }
                    pre = cur;
                    tmp.right = null;
                    cur = cur.right;
                }
            }
        }
        int n = node1.val;
        node1.val = node2.val;
        node2.val = n;
    }
}