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

In this Leetcode problem, we are to return the minimum number of steps to pickup all the apples in an undirected tree, starting from the node 0.

Problem statement

Solution

Here is the draft of ideas to solve the problem recursively:

• Let’s call visit(p) the cost to visit the subtree with root p. For instance, in the above example, visit(1) is 6, visit(4)is 2.
• Let’s call neighbors(p) the children of p in the rooted representation of the tree (root is 0)
• To calculate visit(p), start recursively to compute visit(i) for all i in neighbors(p), and retain the sum in sum
• if sum is not 0, then visit(p) = 2 + sum, we add to for the cost to com from and to the parent of p
• if sum is 0, then if p has an apple return 2, otherwise return 0
• At the top level, 0, the cost of 2 to come from and to the parent doesn’t exists, because 0 doesn’t have a parent, so it should be removed at the end

Here is the full Java code corresponding to the solution:

class Solution {
    public int minTime(
            int n, int[][] edges, List<Boolean> hasApple) {
        Set<Integer> visited = new HashSet<>();
        Map<Integer, Set<Integer>> adjacency = new…