-
Notifications
You must be signed in to change notification settings - Fork 1
Expand file tree
/
Copy pathP_272.java
More file actions
117 lines (103 loc) · 3.46 KB
/
Copy pathP_272.java
File metadata and controls
117 lines (103 loc) · 3.46 KB
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
115
116
117
package leetcode.hard;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;
import utils.DataStructures.TreeNode;
public class P_272 {
public List<Integer> closestKValuesCollect(TreeNode root, double target, int k) {
final LinkedList<Integer> res = new LinkedList<>();
inorder(root, target, k, res);
return res;
}
private static void inorder(TreeNode root, double target, int k, LinkedList<Integer> res) {
if (root == null) {
return;
}
inorder(root.left, target, k, res);
if (res.size() == k) {
if (Math.abs(res.getFirst() - target) > Math.abs(root.val - target)) {
res.pollFirst();
} else {
return;
}
}
res.addLast(root.val);
inorder(root.right, target, k, res);
}
public List<Integer> closestKValues(TreeNode root, double target, int k) {
final Deque<Integer> deque = new ArrayDeque<>();
inorder(root, deque);
while (deque.size() > k) {
if (Math.abs(deque.getFirst() - target) > Math.abs(deque.getLast() - target)) {
deque.pollFirst();
} else {
deque.pollLast();
}
}
return new ArrayList<>(deque);
}
public void inorder(TreeNode root, Deque<Integer> dq) {
if (root == null) {
return;
}
inorder(root.left, dq);
dq.add(root.val);
inorder(root.right, dq);
}
// O(k + log n)
public List<Integer> closestKValuesOptimized(TreeNode root, double target, int k) {
final List<Integer> res = new ArrayList<>();
if (root == null) {
return res;
}
// step 1: find the closet value and save the path
final Deque<TreeNode> lowerStack = new ArrayDeque<>();
final Deque<TreeNode> upperStack = new ArrayDeque<>();
TreeNode p = root;
while (p != null) {
if (p.val < target) {
lowerStack.addFirst(p);
p = p.right;
} else {
upperStack.addFirst(p);
p = p.left;
}
}
for (int i = 0; i < k; i++) {
if (lowerStack.isEmpty()) {
final TreeNode top = upperStack.pop();
res.add(top.val);
goUpperNext(top.right, upperStack);
} else if (upperStack.isEmpty()) {
final TreeNode top = lowerStack.pop();
res.add(top.val);
goLowerNext(top.left, lowerStack);
} else if (upperStack.getFirst().val - target <= target - lowerStack.getFirst().val) {
final TreeNode top = upperStack.pop();
res.add(top.val);
goUpperNext(top.right, upperStack);
} else {
final TreeNode top = lowerStack.pop();
res.add(top.val);
goLowerNext(top.left, lowerStack);
}
}
return res;
}
private static void goUpperNext(TreeNode node, Deque<TreeNode> stack) {
TreeNode p = node;
while (p != null) {
stack.addFirst(p);
p = p.left;
}
}
private static void goLowerNext(TreeNode node, Deque<TreeNode> stack) {
TreeNode p = node;
while (p != null) {
stack.addFirst(p);
p = p.right;
}
}
}