一個樹形結(jié)構(gòu)的公司，所有人的id從0~n-1，老板的ID為headID，每個人有個直屬上司manager[i]（老板的上司-1），每個人需要informTime[i]去通知所有下屬，問如果老板想要通知全公司，最快需要多少時間，DFS
1 #1376
2 #Runtime: 1174 ms (Beats 77.78%)
3 #Memory: 51.1 MB (Beats 38.10%)
4
5 class Solution(object):
6 def numOfMinutes(self, n, headID, manager, informTime):
7 """
8 :type n: int
9 :type headID: int
10 :type manager: List[int]
11 :type informTime: List[int]
12 :rtype: int
13 """
14 son = {}
15 for i in range(n):
16 if manager[i] >= 0:
17 if manager[i] not in son:
18 son[manager[i]] = [i]
19 else:
20 son[manager[i]].append(i)
21
22 def DFS(id):
23 ans = 0
24 if id not in son:
25 return 0
26 for i in son[id]:
27 ans = max(DFS(i), ans)
28 return informTime[id] + ans
29
30 return DFS(headID)