#1443
Minimum Time to Collect All Apples in a Tree
specialist · 660 · lc medium +30 · verified · 63.6% accepted · 3,848 likes · top 66%
Description
An undirected tree of n vertices (numbered 0 to n-1) contains apples at certain nodes. Traversing one edge costs exactly 1 second. Starting and ending at vertex 0, find the minimum number of seconds required to collect all apples.
The tree structure is described by edges where edges[i] = [ai, bi] connects vertices ai and bi. The boolean array hasApple indicates which vertices hold apples (hasApple[i] = true means vertex i has an apple).
Example 1:
Input: n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], hasApple = [false,false,true,false,true,true,false]
Output: 8
Explanation: The figure above represents the given tree where red vertices have an apple. One optimal path to collect all apples is shown by the green arrows.
Example 2:
Input: n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], hasApple = [false,false,true,false,false,true,false]
Output: 6
Explanation: The figure above represents the given tree where red vertices have an apple. One optimal path to collect all apples is shown by the green arrows.
Example 3:
Input: n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], hasApple = [false,false,false,false,false,false,false]
Output: 0
Code
1
2
3