Package g1401_1500.s1443_minimum_time_to_collect_all_apples_in_a_tree

Class Solution

java.lang.Object

g1401_1500.s1443_minimum_time_to_collect_all_apples_in_a_tree.Solution

public class Solution
extends Object

1443 - Minimum Time to Collect All Apples in a Tree\. Medium Given an undirected tree consisting of `n` vertices numbered from `0` to `n-1`, which has some apples in their vertices. You spend 1 second to walk over one edge of the tree. _Return the minimum time in seconds you have to spend to collect all apples in the tree, starting at **vertex 0** and coming back to this vertex._ The edges of the undirected tree are given in the array `edges`, where edges[i] = [ai, bi] means that exists an edge connecting the vertices ai and bi. Additionally, there is a boolean array `hasApple`, where `hasApple[i] = true` means that vertex `i` has an apple; otherwise, it does not have any 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 **Constraints:** * 1 <= n <= 105 * `edges.length == n - 1` * `edges[i].length == 2` * 0 <= ai < bi <= n - 1 * fromi < toi * `hasApple.length == n`

Constructor Summary

Constructors

Constructor	Description
Solution()

Method Summary

Modifier and Type	Method	Description
int	minTime(int n, int[][] edges, List<Boolean> hasApple)

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

Solution

public Solution()

Method Detail

minTime

public int minTime(int n,
                   int[][] edges,
                   List<Boolean> hasApple)