Practice/Meta/Leetcode 1443. Minimum Time to Collect All Apples in a Tree

Leetcode 1443. Minimum Time to Collect All Apples in a Tree

CodingMust

Problem

You are given a tree structure representing an orchard with n nodes numbered from 0 to n-1, where node 0 is the root. The tree is given as an array of edges, where each edge connects two nodes bidirectionally. Some nodes contain fruit that you need to collect.

You start at the root node (node 0) and need to collect all the fruit in the tree, then return to the root. Moving along any edge takes exactly 1 second in either direction.

Your task is to determine the minimum time in seconds needed to collect all fruit and return to the starting position.

Requirements

1. Build the tree structure from the given edges
2. Traverse only the branches that lead to nodes with fruit
3. Calculate the total time by counting each edge that must be traversed
4. Account for the fact that you must return to the root after collecting all fruit

Constraints

• 1 ≤ n ≤ 100,000
• edges.length == n - 1 (valid tree structure)
• edges[i].length == 2
• 0 ≤ edges[i][0], edges[i][1] < n
• hasApple.length == n
• The input represents a valid tree (connected, acyclic)
• Target time complexity: O(n)
• Target space complexity: O(n)

Examples

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: Tree structure: 0 /
1 2 / \ /
4 5 3 6

Nodes 2, 4, and 5 have fruit. Optimal path visits: 0->1->4 (collect), back to 1, 1->5 (collect), back to 0, 0->2 (collect), 2->6 (collect), back to 0. Edges used: (0,1), (1,4), (1,5), (0,2), (2,6) - each traversed twice = 8 seconds total. `

Example 2:

Input: n = 4 edges = [[0,1],[1,2],[0,3]] hasApple = [false,false,false,false] Output: 0 Explanation: No fruit exists in the tree, so no movement is necessary.

Example 3:

Input: n = 3 edges = [[0,1],[0,2]] hasApple = [true,false,false] Output: 0 Explanation: The only fruit is at the root where we start, so no time is needed.