23.01.11 Today’s Leetcode

1443. Minimum Time to Collect All Apples in a Tree (medium)

class Solution:
    def DFS(self, n, edges, hasApple, current, check):
        check_leaf = True
        time = 0
        if check[current]:
            return 0
        else:
            check[current] = True

        for edge in edges:
            a, b = edge[0], edge[1]
            target = None
            if a == current:
                target = b
            if b == current:
                target = a
            if target:
                check_leaf = False
                temp = self.DFS(n, edges, hasApple, target, check)
                if temp > 0:
                    time += temp + 2
                if temp == -1: # first find apple 
                    time += 2
        if hasApple[current]:
            if check_leaf: # leaf apple
                return -1
            elif time == 0: # none-leaf apple
                if current > 0:
                    return -1
        return time

    def minTime(self, n: int, edges: List[List[int]], hasApple: List[bool]) -> int:
        check = [False] * n
        return self.DFS(n, edges, hasApple, 0, check)

class Solution:

    def DFS(self, edges, check, history, current):
        time = 0
        if check[current]: return -1
        else: check[current] = True

        if current == 0 or history[current]:
            history[current] = True
            return 0

        for edge in edges:
            target = None
            if edge[0] == current:
                target = edge[1]
            if edge[1] == current:
                target = edge[0]
            if target:
                time = self.DFS(edges, check, history, target)
                if time >= 0:
                    history[current] = True
                    return time + 1
        return 0

    def minTime(self, n: int, edges: List[List[int]], hasApple: List[bool]) -> int:
        history = [False] * n
        apples = [x for x in range(n) if hasApple[x]]
        res = 0
        for apple in apples:
            check = [False] * n
            temp = self.DFS(edges, check, history, apple)
            res += temp * 2
        return res

class Solution:
    def minTime(self, n: int, edges: List[List[int]], hasApple: List[bool]) -> int:

        tree = defaultdict(list)
        for s,e in edges:
            tree[s].append(e)
            tree[e].append(s)
        
        def dfs(node,par):
            
            res = 0
            for nei in tree[node]:
                if nei != par:
                    res += dfs(nei,node)
            
            if res or hasApple[node]:
                return res + 2

            return res

        return max(dfs(0,-1)-2, 0)