Comment on page

# 99.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
A solution using O(n) space is pretty straight forward.
Could you devise a constant space solution?

## 代码

Approach 1: Sort an Almost Sorted Array Where Two Elements Are Swapped
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public void recoverTree(TreeNode root) {
List<Integer> nums = new ArrayList();
inorder(root, nums);
int[] swapped = findTwoSwapped(nums);
recover(root, 2, swapped[0], swapped[1]);
}
public void inorder(TreeNode root, List<Integer> nums) {
if (root == null) return;
inorder(root.left, nums);
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) {
// second swap occurence
x = nums.get(i);
} 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);
}
}
}

### Approach #2 Iterative Inorder Traversal

Complexity Analysis
• Time complexity : O(1) in the best case, and O(N) in the worst case when one of the swapped nodes is a rightmost leaf.
• Space complexity : up to O(H) to keep the stack where H is a tree height.
class Solution {
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) {
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);
}
public void swap(TreeNode a, TreeNode b) {
int tmp = a.val;
a.val = b.val;
b.val = tmp;
}
}
Approach #3 Recursive Inorder Traversal
class Solution {
TreeNode x = null, y = null, pred = null;
public void recoverTree(TreeNode root) {
findTwoSwapped(root);
swap(x, y);
}
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 swap(TreeNode a, TreeNode b) {
int tmp = a.val;
a.val = b.val;
b.val = tmp;
}
}
Approach #4 Morris Inorder Traversal
class Solution {
public void recoverTree(TreeNode root) {
TreeNode x = null, y = null, pred = null, predecessor = null;
while (root != null) {
if (root.left !== null) {
predecessor = root.left;
while (predecessor.right != null && predecessor.right != root) {
predecessor = predecessor.right;
}
if (predecessor.right == null) {
predecessor.right = root;
root = root.left;
} else {
if (pred != null && root.val < pred.val) {
y = root;
if (x == null) x = pred;
}
pred = root;
predecessor.right = null;
root = root.right;
}
}
}
swap(x , y);
}
public void swap(TreeNode a, TreeNode b) {
int tmp = a.val;
a.val = b.val;
b.val = tmp;
}
}