JZX轻语：简
LeetCode 1443 - 收集树上所有苹果的最少时间
发表于2024年08月22日
不难得知，如果一个子树中没有苹果可摘，那么就没必要经过；否则，进去和出来都要花费2个单位时间(指的是进去和离开这个子树的用时，不包括内部的采摘时间)。因此，我们可以使用DFS进行后序遍历，递归计算每个子树所需的采摘时间。如果子树中至少一个子树有苹果可摘(即返回值不为0)，或者当前子树的根节点有苹果，则消耗时间为2 + 所有子树的采摘时间；否则，消耗时间为0。最后，返回从根节点出发的总采摘时间即可。
需要注意的是，对于根节点，没必要+2，因为根节点作为起点，不需要进入。
class Solution:
def minTime(self, n: int, edges: List[List[int]], hasApple: List[bool]) -> int:
adj_list = [[] for _ in range(n)]
for u, v in edges:
adj_list[u].append(v)
adj_list[v].append(u)
def dfs(cur: int, pa: int):
res = 0
for child in adj_list[cur]:
if child == pa:
continue
res += dfs(child, cur)
# 判断当前子树是否需要进去采摘，如果需要，根据其是否为根节点，加上进出的时间
# 根节点不需要+2，非根节点中，自身有苹果`hasApple[cur] == True`或者子树有苹果`res > 0`，需要进去采摘
if (hasApple[cur] or res) and cur != 0:
res += 2
return res
return dfs(0, -1)