@@ -0,0 +1,3215 @@
+/***%0A * Two elements of a binary search tree (BST) are swapped by mistake.%0A *%0A * Recover the tree without changing its structure.%0A *%0A * Note:%0A * A solution using O(n) space is pretty straight forward. Could you devise a constant space solution?%0A */%0A/**%0A * Definition for binary tree%0A * public class TreeNode %7B%0A *     int val;%0A *     TreeNode left;%0A *     TreeNode right;%0A *     TreeNode(int x) %7B val = x; %7D%0A * %7D%0A*/%0Aimport java.util.List;%0Aimport java.util.ArrayList;%0A%0A// Inorder traversal to find illegal ones, then swap them.%0Apublic class Solution %7B%0A    // Solution 1: O(n)%0A    // Using list to record all nodes%0A    /*%0A    public void recoverTree(TreeNode root) %7B%0A        List%3CTreeNode%3E nlist = new ArrayList%3CTreeNode%3E();%0A        inorderTraversal(root, nlist);%0A        TreeNode a = null, b = null;%0A        int i = 0, j;%0A        for (; i %3C nlist.size() - 1; i++)%0A            if (nlist.get(i).val %3E nlist.get(i + 1).val) %7B%0A                a = nlist.get(i);%0A                break;%0A            %7D%0A        for (j = i + 2; j %3C nlist.size(); j++)%0A            if (nlist.get(j - 1).val %3E nlist.get(j).val) %7B%0A                b = nlist.get(j);%0A                break;%0A            %7D%0A        if (b == null)%0A            b = nlist.get(i + 1);%0A        int temp = a.val;%0A        a.val = b.val;%0A        b.val = temp;%0A    %7D%0A%0A    private void inorderTraversal(TreeNode root, List%3CTreeNode%3E list) %7B%0A        if (root == null)%0A            return;%0A        inorderTraversal(root.left, list);%0A        list.add(root);%0A        inorderTraversal(root.right, list);%0A    %7D%0A    */%0A%0A    // Solution 2: O(n), O(1)%0A    // Based on Morris Inorder Traversal%0A    public class Pair%3CF, S%3E %7B%0A        private F first;%0A        private S second;%0A    %7D%0A    public void recoverTree(TreeNode root) %7B%0A        Pair%3CTreeNode, TreeNode%3E broken = new Pair%3CTreeNode, TreeNode%3E();%0A        TreeNode prev = null;%0A        TreeNode cur = root;%0A        while (cur != null) %7B%0A            if (cur.left == null) %7B%0A                detect(broken, prev, cur);%0A                prev = cur;%0A                cur = cur.right;%0A            %7D else %7B%0A                TreeNode node = cur.left;%0A                while(node.right != null && node.right != cur)%0A                    node = node.right;%0A%0A                if (node.right == null) %7B // Construct threading%0A                    node.right = cur;%0A                    cur = cur.left;%0A                %7D else %7B // node.right == cur, visit threading%0A                    /*      3%0A                     *     /'%0A                     *    1 '%0A                     *     %5C'%0A                     *      2%0A                     */%0A                    detect(broken, prev, cur);%0A                    node.right = null; // Remove threading%0A                    prev = cur;%0A                    cur = cur.right;%0A                %7D%0A            %7D%0A        %7D%0A        int temp = broken.first.val;%0A        broken.first.val = broken.second.val;%0A        broken.second.val = temp;%0A    %7D%0A    private void detect(Pair%3CTreeNode, TreeNode%3E broken, TreeNode prev, TreeNode cur) %7B%0A        if (prev != null && prev.val %3E cur.val) %7B%0A            if (broken.first == null) %7B%0A                broken.first = prev;%0A            %7D%0A            broken.second = cur;%0A        %7D%0A    %7D%0A%7D%0A

add RecoverBinarySearchTree.java