Daily Archives: August 1, 2016

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.

Given a sorted array. Two elements are swapped. Recover this array.

Solution. Think about the case1:

Original array = [1, 2, 3, 4, 5, 6, 7].

Swapped array = [1, 7, 3, 4, 5, 6, 2].

And we have first and second with Integer type. In this way, we know
If arr[i] > arr[i + 1] and first == null, we have first = i.
If arr[i] > arr[i + 1] and first != null, we have second = i + 1

Another exception case happens when the swapped element are together:

Original array = [1, 2, 3, 4, 5, 6, 7].

Swapped array = [1, 3, 2, 4, 5, 6, 7].

In this way,
If arr[i] > arr[i + 1] and first == null, we have first = i, second = i + 1

Considering above 2 cases, below is a concise code for it:

public static void recoverArray(int[] arr) {
    Integer first = null, second = null;
    for (int i = 0; i < arr.length - 1; i++) {
        if (arr[i] > arr[i + 1]) {
            if (first == null) {
                first = i;
            }
            second = i + 1;
        }
    }
    int tmp = arr[first];
    arr[first] = arr[second];
    arr[second] = tmp;
}

Check my code on github.