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 int minTime(int n, int[][] edges, List<Boolean> hasApple) {
Map<Integer, List<Integer>> nodeNeighbors = new HashMap<>();
for (int[] edge : edges) {
nodeNeighbors.computeIfAbsent(edge[0], (key) -> new ArrayList<>()).add(edge[1]);
nodeNeighbors.computeIfAbsent(edge[1], (key) -> new ArrayList<>()).add(edge[0]);
}
int path = dfs(0, nodeNeighbors, hasApple, new HashSet<>());
return path == 0 ? path : path - 2;
}
private int dfs(int currNode, Map<Integer, List<Integer>> nodeNeighbors, List<Boolean> hasApple,
Set<Integer> visited) {
visited.add(currNode);
int path = 0;
for (int neighbor : nodeNeighbors.get(currNode)) {
if (!visited.contains(neighbor)) {
int subtreePath = dfs(neighbor, nodeNeighbors, hasApple, visited);
path += subtreePath;
}
}
if (hasApple.get(currNode) || path != 0) {
path += 2;
}
visited.remove(currNode);
return path;
}
}
|
递归函数的作用就是告诉我们从当前node出发把左或者右树中的apple摘取完需要的path是多少.这里把subtree的苹果摘完返回到subtree的root不算完还要返回该root的parent, 等于是从parent就开始记录然后再回到parent需要的步数.
如果一个subtree中没有苹果, 那么返回0, 否则返回一个正数. 因此我们在main函数中调用该递归函数时需要判断返回的值, 如果是0, 那就说明给的树中没有苹果, 返回0即可; 如果大于0, 我们要手动-2, 因为所在的main函数等效于我们在一个parent node中向root调用, 因此要减去2.
时间复杂度: O(n)
空间复杂度: O(n)
