This is No.99 in LeetCode.
Here are approaches to this problem:
Approach 1: Sort an Almost Sorted Array Where Two Elements Are Swapped
Algorithm
Here is the algorithm:
-
Construct inorder traversal of the tree. It should be an almost sorted list where only two elements are swapped.
-
Identify two swapped elements x and y in an almost sorted array in linear time.
-
Traverse the tree again. Change value x to y and value y to x.
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]);
}
}
Approach 2: Iterative Inorder Traversal
class Solution {
public void swap(TreeNode a, TreeNode b) {
int tmp = a.val;
a.val = b.val;
b.val = tmp;
}
public void recoverTree(TreeNode root) {
Deque<TreeNode> stack = new ArrayDeque();
TreeNode x = null, y = null, pred = null;
while (!stack.isEmpty() || root != null) {
while (root != null) {
stack.add(root);
root = root.left;
}
root = stack.removeLast();
if (pred != null && root.val < pred.val) {
y = root;
if (x == null) x = pred;
else break;
}
pred = root;
root = root.right;
}
swap(x, y);
}
}
Approach 3: Recursive Inorder Traversal
This is recursion version of approach 2.
class Solution {
TreeNode x = null, y = null, pred = null;
public void swap(TreeNode a, TreeNode b) {
int tmp = a.val;
a.val = b.val;
b.val = tmp;
}
public void findTwoSwapped(TreeNode root) {
if (root == null) return;
findTwoSwapped(root.left);
if (pred != null && root.val < pred.val) {
y = root;
if (x == null) x = pred;
else return;
}
pred = root;
findTwoSwapped(root.right);
}
public void recoverTree(TreeNode root) {
findTwoSwapped(root);
swap(x, y);
}
}