#Problem

#⭐️⭐️⭐️

找Closest leaf

#Solution

没什么技巧, 构图+BFS

#Code

#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
class Solution {
public int findClosestLeaf(TreeNode root, int k) {
if (root == null) return 0;
final Map<Integer, Set<Integer>> graph = new HashMap<>();
final Map<Integer, TreeNode> index = new HashMap<>();
traversal(root, graph, index);
return bfs(k, graph, index);
}
private int bfs(final int root, final Map<Integer, Set<Integer>> graph, final Map<Integer, TreeNode> index) {
final Set<Integer> isVisited = new HashSet<>();
final Queue<Integer> queue = new LinkedList<>();
queue.add(root);
int depth = 0;
while (!queue.isEmpty()) {
depth++;
final int size = queue.size();
for (int i = 0; i < size; i++) {
final int curr = queue.poll();
isVisited.add(curr);
final TreeNode currNode = index.get(curr);
if (currNode.left == null && currNode.right == null) return curr;
for (final int adj : graph.get(curr)) {
if (!isVisited.contains(adj)) {
queue.add(adj);
}
}
}
}
return -1;
}
private void traversal(final TreeNode root, final Map<Integer, Set<Integer>> graph, Map<Integer, TreeNode> index) {
if (root == null) return;
graph.putIfAbsent(root.val, new HashSet<>());
index.put(root.val, root);
if (root.left != null) {
graph.putIfAbsent(root.left.val, new HashSet<>());
graph.get(root.val).add(root.left.val);
graph.get(root.left.val).add(root.val);
traversal(root.left, graph, index);
}
if (root.right != null) {
graph.putIfAbsent(root.right.val, new HashSet<>());
graph.get(root.val).add(root.right.val);
graph.get(root.right.val).add(root.val);
traversal(root.right, graph, index);
}
}
}

Comments