#Problem

#⭐️⭐️⭐️⭐️

All Nodes Distance K in Binary Tree

#Solution

披着二叉树外套的graph题..

构建graph然后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
class Solution {
public List<Integer> distanceK(TreeNode root, TreeNode target, int K) {
final List<Integer> res = new ArrayList<>();
if (root == null || target == null) return res;
if (K == 0) {
res.add(target.val);
return res;
}
final Map<Integer, Set<Integer>> graph = new HashMap<>();
dfs(root, null, graph);
bfs(target.val, -1, graph, new HashSet<>(), K, res);
return res;
}
private void dfs(final TreeNode root, final TreeNode parent, final Map<Integer, Set<Integer>> graph) {
if (root == null) return;
graph.putIfAbsent(root.val, new HashSet<>());
if (parent != null) {
graph.get(parent.val).add(root.val);
graph.get(root.val).add(parent.val);
}
dfs(root.left, root, graph);
dfs(root.right, root, graph);
}
private void bfs(final int curr, final int parent, final Map<Integer, Set<Integer>> graph, final Set<Integer> visited, final int K, final List<Integer> res) {
if (K == 0) {
res.add(curr);
return;
}
visited.add(curr);
for (final int adj : graph.get(curr)) {
if (adj != parent && !visited.contains(adj)) {
bfs(adj, curr, graph, visited, K - 1, res);
}
}
}
}

Comments