dev/leetcode/recoverbinarytree

Recover Binary Search Tree

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

Recover the tree without changing its structure.

Example 1:

Input: [1,3,null,null,2]

1
/
3

2

Output: [3,1,null,null,2]

3
/
1

2
Example 2:

Input: [3,1,4,null,null,2]

3
/
1 4
/
2

Output: [2,1,4,null,null,3]

2
/
1 4
/
3
Follow up:

A solution using O(n) space is pretty straight forward.
Could you devise a constant space solution?

Unsolved

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution {
public void inorder(TreeNode root, List<Integer> nums) {
if (root == null) return;
inorder(root.left, nums);
nums.add(root.val);
inorder(root.right, nums);
}

public int[] findTwoSwapped(List<Integer> nums) {
int n = nums.size();
int x = -1, y = -1;
for(int i = 0; i < n - 1; ++i) {
if (nums.get(i + 1) < nums.get(i)) {
y = nums.get(i + 1);
// first swap occurence
if (x == -1) x = nums.get(i);
// second swap occurence
else break;
}
}
return new int[]{x, y};
}

public void recover(TreeNode r, int count, int x, int y) {
if (r != null) {
if (r.val == x || r.val == y) {
r.val = r.val == x ? y : x;
if (--count == 0) return;
}
recover(r.left, count, x, y);
recover(r.right, count, x, y);
}
}

public void recoverTree(TreeNode root) {
List<Integer> nums = new ArrayList();
inorder(root, nums);
int[] swapped = findTwoSwapped(nums);
recover(root, 2, swapped[0], swapped[1]);
}
}

Reference
https://leetcode-cn.com/problems/recover-binary-search-tree