1443. Minimum Time to Collect All Apples in a Tree

Problem Statement

link: LeetCode.cn LeetCode 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:

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

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

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 Approach

The solution uses Depth-First Search (DFS) to traverse the tree and calculate the minimum time required to collect all apples by summing up the necessary steps for nodes that either have apples or lead to nodes with apples.

Algorithm

1. Tree Construction: Build an adjacency list representation of the tree from the given edges for easy traversal.
2. DFS Traversal: Use DFS to explore each node, calculating the time required to collect apples from child nodes and accumulate the steps.
3. Result Calculation: The total time is doubled (for the round trip), and the DFS returns only the necessary time, subtracting the final unnecessary step back to the root if no apples are collected beyond a certain node.

Implement

    class Solution:
  def minTime(self, n: int, edges: List[List[int]], hasApple: List[bool]) -> int:
      def dfs(node, parent):
          steps = 0
          for child in adj[node]:  
              if child != parent: 
                  steps += dfs(child, node) 
    
          return steps + 2 if steps or hasApple[node] else 0 #node0  6
      
      adj = defaultdict(list)
      for a, b in edges:
          adj[a].append(b)
          adj[b].append(a)
          
      result = dfs(0, None)        
      return result - 2 if result else 0

    
    

Twitter  facebook  Email