-
Notifications
You must be signed in to change notification settings - Fork 1
/
LeetCode-99-Recover-Binary-Search-Tree.java
114 lines (98 loc) · 3.5 KB
/
LeetCode-99-Recover-Binary-Search-Tree.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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
/*
Space: O(N)
Time: O(N)
https://leetcode.com/problems/recover-binary-search-tree/discuss/32535/No-Fancy-Algorithm-just-Simple-and-Powerful-In-Order-Traversal
In-order traversal: 6, 3, 4, 5, 2
first = 6
second = 2
swap(first, second)
*/
// public void recoverTree(TreeNode root) {
// if (root == null) return;
// TreeNode curr = root;
// TreeNode firstElement = null, secondElement = null, prev = null;
// Stack<TreeNode> stack = new Stack<>();
// while (curr != null || !stack.isEmpty()) {
// if (curr != null) {
// stack.push(curr);
// curr = curr.left;
// } else {
// curr = stack.pop();
// if (prev != null && firstElement == null && prev.val > curr.val) {
// firstElement = prev;
// }
// if (prev != null && firstElement != null && prev.val > curr.val) {
// secondElement = curr;
// }
// prev = curr;
// curr = curr.right;
// }
// }
// // swap the value of first and second element
// int temp = firstElement.val;
// firstElement.val = secondElement.val;
// secondElement.val = temp;
// }
/*
Morris Traversal
Space: O(1)
Time: O(N)
*/
public void recoverTree(TreeNode root) {
if (root == null) return;
TreeNode curr = root;
TreeNode prev = null, firstElement = null, secondElement = null;
while (curr != null) {
if (curr.left == null) {
if (prev != null && firstElement == null && prev.val > curr.val) {
firstElement = prev;
}
if (prev != null && firstElement != null && prev.val > curr.val) {
secondElement = curr;
}
prev = curr;
curr = curr.right;
} else {
TreeNode predecessor = curr.left;
while (predecessor.right != null && predecessor.right != curr) {
predecessor = predecessor.right;
}
if (predecessor.right == null) {
predecessor.right = curr;
curr = curr.left;
} else {
// process curr node
if (prev != null && firstElement == null && prev.val > curr.val) {
firstElement = prev;
}
if (prev != null && firstElement != null && prev.val > curr.val) {
secondElement = curr;
}
predecessor.right = null;
prev = curr;
curr = curr.right;
}
}
}
// swap the value of first and second element
int temp = firstElement.val;
firstElement.val = secondElement.val;
secondElement.val = temp;
}
}