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? 

 

找个二叉搜索树中出错的两个元素，交换位置来恢复二叉搜索树。同时题目要求只用常数空间复杂度，普通的遍历方式使用了栈或者递归，因此在空间复杂度上不满足要求。这里使用Morris Traversal，简单的说就是充分利用二叉树的叶子节点，使叶子节点的又指针指向在中序遍历中的后继节点。关于Morris Traversal的详细介绍，参考这篇博文。

我们先来实现一个Morris Traversal遍历的代码：

public void morrisTraversal(TreeNode root) {        if(root == null) return;        TreeNode pre = new TreeNode(Integer.MIN_VALUE);while(root != null) {            if(root.left != null) {                TreeNode tmp = root.left;                while(tmp.right!=null && tmp.right!=root)                    tmp = tmp.right;                if(tmp.right == null) {                    tmp.right = root;                    root = root.left;                } else {                    tmp.right = null;                    System.out.println(root.val); //业务逻辑                    root = root.right;                }            } else {                System.out.println(root.val); //业务逻辑                root = root.right;            }        }    }

上述代码使用Morris Traversal实现了二叉树的中序遍历。其中两处System.out.println(root.val)是中序遍历的业务处理部分。在本题中，我们需要找到出错的两处节点，只要修改这两处业务逻辑即可。修改后的代码如下：

public void recoverTree(TreeNode root) {        if(root == null) return;        TreeNode pre = new TreeNode(Integer.MIN_VALUE);        TreeNode error1 = null;        TreeNode error2 = null;        while(root != null) {            if(root.left != null) {                TreeNode tmp = root.left;                while(tmp.right!=null && tmp.right!=root)                    tmp = tmp.right;                if(tmp.right == null) {                    tmp.right = root;                    root = root.left;                } else {                    tmp.right = null；//find error                    if(root.val < pre.val) {                        if(error1 == null) error1 = pre;                        error2 = root;                    }                     pre = root;                                        //System.out.println(root.val);                    root = root.right;                }            } else {                //find error                if(root.val < pre.val) {                    if(error1 == null) error1 = pre;                    error2 = root;                }                 pre = root;                                //System.out.println(root.val);                root = root.right;            }        }                if(error1 != null && error2 != null) {            int tmp = error1.val;            error1.val = error2.val;            error2.val = tmp;        }    }

上述代码中，我们用error1和error2指向两个出错的节点，并在循环结束后将两个节点的内容互换来恢复二叉树。