1443. Minimum Time to Collect All Apples in a Tree

Problem

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

• hasApple.length == n

Solution

/**
 * @param {number} n
 * @param {number[][]} edges
 * @param {boolean[]} hasApple
 * @return {number}
 */
var minTime = function(n, edges, hasApple) {
    var nodeMap = Array(n).fill(0).map(() => []);
    for (var i = 0; i < edges.length; i++) {
        nodeMap[edges[i][0]].push(edges[i][1]);
        nodeMap[edges[i][1]].push(edges[i][0]);
    }
    return dfs(0, nodeMap, hasApple, Array(n))[1];
};

var dfs = function(root, nodeMap, hasApple, visited) {
    if (visited[root]) return [false, 0];
    var has = hasApple[root];
    var time = 0;
    visited[root] = true;
    for (var i = 0; i < nodeMap[root].length; i++) {
        var item = dfs(nodeMap[root][i], nodeMap, hasApple, visited);
        if (item[0]) {
            has = true;
            time += item[1] + 2;
        }
    }
    return [has, time];
};

Explain:

nope.

Complexity:

• Time complexity : O(n).
• Space complexity : O(n).