Skip to content

General Tree Top-Down DFS

Table of Contents

1376. Time Needed to Inform All Employees

1376. Time Needed to Inform All Employees - Python Solution
from collections import defaultdict, deque
from typing import List


# DFS
def numOfMinutesDFS(
    n: int, headID: int, manager: List[int], informTime: List[int]
) -> int:
    graph = defaultdict(list)
    for i in range(n):
        if manager[i] != -1:
            graph[manager[i]].append(i)

    def dfs(node):
        time = 0
        for sub in graph[node]:
            time = max(time, dfs(sub))
        return time + informTime[node]

    return dfs(headID)


# BFS
def numOfMinutesBFS(
    n: int, headID: int, manager: List[int], informTime: List[int]
) -> int:
    graph = defaultdict(list)
    for i in range(n):
        if manager[i] != -1:
            graph[manager[i]].append(i)

    q = deque([(headID, 0)])
    max_time = 0

    while q:
        node, time = q.popleft()
        max_time = max(max_time, time)
        for sub in graph[node]:
            q.append((sub, time + informTime[node]))

    return max_time


n = 6
headID = 2
manager = [2, 2, -1, 2, 2, 2]
informTime = [0, 0, 1, 0, 0, 0]
print(numOfMinutesDFS(n, headID, manager, informTime))  # 1
print(numOfMinutesBFS(n, headID, manager, informTime))  # 1

1443. Minimum Time to Collect All Apples in a Tree

  • LeetCode | LeetCode CH (Medium)

  • Tags: hash table, tree, depth first search, breadth first search

1377. Frog Position After T Seconds

3067. Count Pairs of Connectable Servers in a Weighted Tree Network

3372. Maximize the Number of Target Nodes After Connecting Trees I

2467. Most Profitable Path in a Tree

  • LeetCode | LeetCode CH (Medium)

  • Tags: array, tree, depth first search, breadth first search, graph

3373. Maximize the Number of Target Nodes After Connecting Trees II

1766. Tree of Coprimes

3425. Longest Special Path

  • LeetCode | LeetCode CH (Hard)

  • Tags: array, hash table, tree, depth first search, sliding window

2791. Count Paths That Can Form a Palindrome in a Tree

  • LeetCode | LeetCode CH (Hard)

  • Tags: dynamic programming, bit manipulation, tree, depth first search, bitmask

Comments