Recover Binary Search Tree

leetcode 99.

Two elements of a binary search tree (BST) are swapped by mistake.

Recover the tree without changing its structure.

Solution. This problem is a difficult one. If we want to solve it in O(n) time and O(1) space, we need Morris Traversal. Besides, we need a decent code to find the swapped position in sorted array. Refer these two posts for detail: Morris Traversal, Recover Sorted Array

public static void recoverTree(TreeNode root) {
    TreeNode pre = null, curr = root, first = null, second = null;
    while (curr != null) {
        if (curr.left == null) {    // pop point and compare
            if (pre != null && curr.val < pre.val) {
                if (first == null) {
                    first = pre;
                }
                second = curr;
            }
            pre = curr;
            curr = curr.right;
            continue;
        }
        TreeNode rightMost = curr.left;
        while (rightMost.right != null && rightMost.right != curr) {
            rightMost = rightMost.right;
        }
        if (rightMost.right == null) {
            rightMost.right = curr;
            curr = curr.left;
        }
        else {
            if (pre != null && curr.val < pre.val) {
                if (first == null) {
                    first = pre;
                }
                second = curr;
            }
            pre = curr;
            curr = curr.right;
            rightMost.right = null;
        }
    }
    int val = first.val;
    first.val = second.val;
    second.val = val;
}

Check my code on github.