-
Notifications
You must be signed in to change notification settings - Fork 1
/
RecoverBinarySearchTree.java
41 lines (37 loc) · 1.2 KB
/
RecoverBinarySearchTree.java
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
/**
* 99. Recover Binary Search Tree
*
* 1. 二叉搜索树,中序遍历就是有序数组。
* 2. 一个「交换了两个元素」的有序数组,是有模版在 O(n) 时间内找出被交换的元素x和y。
* - 第一次遇到cur<prev时,确定x;第二次遇到时,确定y。
*
* @author LBW
*/
public class RecoverBinarySearchTree {
private TreeNode prev; // prev represents the last accessed treenode.
private TreeNode x = null, y = null; // x and y represent two elements
public void recoverTree(TreeNode root) {
inOrderTraversal(root); // find x and y in the traversal.
swap(x, y); // swap x and y.
}
private void inOrderTraversal(TreeNode root) {
if (root == null)
return;
inOrderTraversal(root.left);
//find the two swapped elements: x and y.
if ((prev != null) && (root.val < prev.val)) {
y = root;
if (x == null)
x = prev;
else
return;
}
prev = root;
inOrderTraversal(root.right);
}
private void swap(TreeNode x, TreeNode y) {
int temp = x.val;
x.val = y.val;
y.val = temp;
}
}