Binary Search(TLE)
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
| class Solution {
public List<List<Integer>> closestNodes(TreeNode root, List<Integer> queries) {
List<List<Integer>> resultList = new ArrayList<>(queries.size());
for (int query : queries) {
List<Integer> minMaxList = new ArrayList<>(2);
minMaxList.add(-1);
minMaxList.add(-1);
search(minMaxList, root, query);
resultList.add(minMaxList);
}
return resultList;
}
private void search(List<Integer> minMaxList, TreeNode node, int query) {
if (node == null) {
return;
}
if (query == node.val) {
minMaxList.set(0, query);
minMaxList.set(1, query);
return;
}
if (query < node.val) {
minMaxList.set(1, node.val);
search(minMaxList, node.left, query);
} else {
minMaxList.set(0, node.val);
search(minMaxList, node.right, query);
}
}
}
|
注意题目不保证二叉搜索树是平衡的，故以上解法在极端情况下搜索的时间复杂度会退化为 O(n)，导致超时。
TreeMap
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
| class Solution {
public List<List<Integer>> closestNodes(TreeNode root, List<Integer> queries) {
TreeSet<Integer> treeSet = new TreeSet<>();
dfs(treeSet, root);
List<List<Integer>> resultList = new ArrayList<>(queries.size());
for (int query : queries) {
List<Integer> minMaxList = new ArrayList<>(2);
Integer min = treeSet.floor(query);
minMaxList.add(min == null ? -1 : min);
Integer max = treeSet.ceiling(query);
minMaxList.add(max == null ? -1 : max);
resultList.add(minMaxList);
}
return resultList;
}
private void dfs(TreeSet<Integer> treeSet, TreeNode node) {
if (node == null) {
return;
}
treeSet.add(node.val);
dfs(treeSet, node.left);
dfs(treeSet, node.right);
}
}
|
使用 TreeSet 将二叉搜索树变平衡，以解决不平衡导致搜索慢的问题。
Binary Search
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
| class Solution {
public List<List<Integer>> closestNodes(TreeNode root, List<Integer> queries) {
List<Integer> numList = new ArrayList<>();
dfs(numList, root);
List<List<Integer>> resultList = new ArrayList<>(queries.size());
for (int query : queries) {
List<Integer> minMaxList = new ArrayList<>(2);
minMaxList.add(searchFloor(numList, query));
minMaxList.add(searchCeiling(numList, query));
resultList.add(minMaxList);
}
return resultList;
}
private Integer searchCeiling(List<Integer> numList, int query) {
if (numList.get(numList.size() - 1) < query) {
return -1;
}
int i = 0, j = numList.size() - 1;
while (i < j) {
int mid = (i + j) >>> 1;
if (numList.get(mid) >= query) {
j = mid;
} else {
i = mid + 1;
}
}
return numList.get(i);
}
private Integer searchFloor(List<Integer> numList, int query) {
if (numList.get(0) > query) {
return -1;
}
int i = 0, j = numList.size() - 1;
while (i < j) {
int mid = (i + j + 1) >>> 1;
if (numList.get(mid) <= query) {
i = mid;
} else {
j = mid - 1;
}
}
return numList.get(i);
}
private void dfs(List<Integer> numList, TreeNode node) {
if (node == null) {
return;
}
dfs(numList, node.left);
numList.add(node.val);
dfs(numList, node.right);
}
}
|
Binary Search
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
| class Solution {
public List<List<Integer>> closestNodes(TreeNode root, List<Integer> queries) {
List<Integer> numList = new ArrayList<>();
dfs(numList, root);
List<List<Integer>> resultList = new ArrayList<>(queries.size());
for (int query : queries) {
List<Integer> minMaxList = new ArrayList<>(2);
int floorIndex = searchFloor(numList, query);
if (floorIndex == -1) {
minMaxList.add(-1);
minMaxList.add(numList.get(0));
} else {
minMaxList.add(numList.get(floorIndex));
if (minMaxList.get(0) == query) {
minMaxList.add(minMaxList.get(0));
} else {
minMaxList.add(floorIndex + 1 == numList.size() ? -1 : numList.get(floorIndex + 1));
}
}
resultList.add(minMaxList);
}
return resultList;
}
private Integer searchFloor(List<Integer> numList, int query) {
if (numList.get(0) > query) {
return -1;
}
int i = 0, j = numList.size() - 1;
while (i < j) {
int mid = (i + j + 1) >>> 1;
if (numList.get(mid) <= query) {
i = mid;
} else {
j = mid - 1;
}
}
return i;
}
private void dfs(List<Integer> numList, TreeNode node) {
if (node == null) {
return;
}
dfs(numList, node.left);
numList.add(node.val);
dfs(numList, node.right);
}
}
|
因小于等于 queries[i] 的最大值与大于等于 queries[i] 的最小值相邻，故可优化为仅寻找最大值来实现，相比上方解法减少了对最小值的搜索，注意处理临界值，如最大值或最小值不存在的场景，最大值与最小值相同的场景。
References
2476. Closest Nodes Queries in a Binary Search Tree