@@ -0,0 +1,1423 @@
+package problems;%0A%0Apublic class RecoverBinarySearchTree %7B%0A%0A    public class TreeNode %7B%0A        int val;%0A        TreeNode left, right;%0A%0A        TreeNode(int x) %7B%0A            val = x;%0A        %7D%0A    %7D%0A%0A    // O(n) time and O(1) space, Morris traversal.%0A    public void recoverTree(TreeNode root) %7B%0A        TreeNode cur = root, pre = null, n1 = null, n2 = null;%0A        while (cur != null) %7B%0A            if (cur.left == null) %7B%0A                if (pre != null && pre.val %3E cur.val) %7B%0A                    if (n1 == null)%0A                        n1 = pre;%0A                    n2 = cur;%0A                %7D%0A                pre = cur;%0A                cur = cur.right;%0A            %7D else %7B%0A                TreeNode t = cur.left;%0A                while (t.right != null && t.right != cur)%0A                    t = t.right;%0A                if (t.right == null) %7B%0A                    t.right = cur;%0A                    cur = cur.left;%0A                %7D else %7B%0A                    t.right = null;%0A                    if (pre != null && pre.val %3E cur.val) %7B%0A                        if (n1 == null)%0A                            n1 = pre;%0A                        n2 = cur;%0A                    %7D%0A                    pre = cur;%0A                    cur = cur.right;%0A                %7D%0A            %7D%0A        %7D%0A        if (n1 != null && n2 != null) %7B%0A            int t = n1.val;%0A            n1.val = n2.val;%0A            n2.val = t;%0A        %7D%0A    %7D%0A%7D%0A

Add Recovery Binary Search Tree