LeetCode 题解工作台
收集树上所有苹果的最少时间
给你一棵有 n 个节点的无向树，节点编号为 0 到 n-1 ，它们中有一些节点有苹果。通过树上的一条边，需要花费 1 秒钟。你从 节点 0 出发，请你返回最少需要多少秒，可以收集到所有苹果，并回到节点 0 。 无向树的边由 edges 给出，其中 edges[i] = [from i , to i …
4
题型
4
代码语言
3
相关题
当前训练重点
中等 · 二分·树·traversal
答案摘要
class Solution: def minTime(self, n: int, edges: List[List[int]], hasApple: List[bool]) -> int:
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 二分·树·traversal 题型思路
题目描述
给你一棵有 n 个节点的无向树，节点编号为 0 到 n-1 ，它们中有一些节点有苹果。通过树上的一条边，需要花费 1 秒钟。你从 节点 0 出发，请你返回最少需要多少秒，可以收集到所有苹果，并回到节点 0 。
无向树的边由 edges 给出，其中 edges[i] = [fromi, toi] ，表示有一条边连接 from 和 toi 。除此以外，还有一个布尔数组 hasApple ，其中 hasApple[i] = true 代表节点 i 有一个苹果，否则，节点 i 没有苹果。
示例 1：
输入：n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], hasApple = [false,false,true,false,true,true,false] 输出：8 解释：上图展示了给定的树，其中红色节点表示有苹果。一个能收集到所有苹果的最优方案由绿色箭头表示。
示例 2：
输入：n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], hasApple = [false,false,true,false,false,true,false] 输出：6 解释：上图展示了给定的树，其中红色节点表示有苹果。一个能收集到所有苹果的最优方案由绿色箭头表示。
示例 3：
输入：n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], hasApple = [false,false,false,false,false,false,false] 输出：0
提示：
1 <= n <= 10^5edges.length == n - 1edges[i].length == 20 <= ai < bi <= n - 1hasApple.length == n
解题思路
方法一：DFS
class Solution:
def minTime(self, n: int, edges: List[List[int]], hasApple: List[bool]) -> int:
def dfs(u, cost):
if vis[u]:
return 0
vis[u] = True
nxt_cost = 0
for v in g[u]:
nxt_cost += dfs(v, 2)
if not hasApple[u] and nxt_cost == 0:
return 0
return cost + nxt_cost
g = defaultdict(list)
for u, v in edges:
g[u].append(v)
g[v].append(u)
vis = [False] * n
return dfs(0, 0)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
The candidate demonstrates familiarity with tree traversal techniques.
- question_mark
The candidate optimizes traversal by focusing only on paths with apples.
- question_mark
The candidate shows ability to backtrack and minimize unnecessary traversal.
常见陷阱
外企场景- error
Failing to track apple-containing nodes properly, leading to unnecessary traversal.
- error
Not considering the time spent traveling back to the root after collecting apples.
- error
Overcomplicating the solution by adding unnecessary checks or conditions.
进阶变体
外企场景- arrow_right_alt
Handling larger trees with up to 10^5 vertices and ensuring efficiency.
- arrow_right_alt
Modifying the problem to return the path taken instead of just the time.
- arrow_right_alt
Considering additional constraints such as limits on the number of edges per node.