1376. 通知所有员工所需的时间
公司里有
n
名员工，每个员工的 ID 都是独一无二的，编号从
0
到
n - 1
。公司的总负责人通过
headID
进行标识。
在
manager
数组中，每个员工都有一个直属负责人，其中
manager[i]
是第
i
名员工的直属负责人。对于总负责人，
manager[headID] = -1
。题目保证从属关系可以用树结构显示。
公司总负责人想要向公司所有员工通告一条紧急消息。他将会首先通知他的直属下属们，然后由这些下属通知他们的下属，直到所有的员工都得知这条紧急消息。
第
i
名员工需要
informTime[i]
分钟来通知它的所有直属下属（也就是说在
informTime[i]
分钟后，他的所有直属下属都可以开始传播这一消息）。
返回通知所有员工这一紧急消息所需要的
分钟数
。
示例 1：
输入：n = 1, headID = 0, manager = [-1], informTime = [0] 输出：0 解释：公司总负责人是该公司的唯一一名员工。
示例 2：
输入：n = 6, headID = 2, manager = [2,2,-1,2,2,2], informTime = [0,0,1,0,0,0] 输出：1 解释：id = 2 的员工是公司的总负责人，也是其他所有员工的直属负责人，他需要 1 分钟来通知所有员工。 上图显示了公司员工的树结构。
提示：
-
1 <= n <= 10^5
-
0 <= headID < n
-
manager.length == n
-
0 <= manager[i] < n
-
manager[headID] == -1
-
informTime.length == n
-
0 <= informTime[i] <= 1000
-
如果员工
i
没有下属，
informTime[i] == 0
。 -
题目
保证
所有员工都可以收到通知。
解题思路：
这是一个树形结构问题，需要通过遍历树来求解。
方法一：可以使用深度优先搜索（DFS）来遍历树
方法二：可以使用广度优先搜索（BFS）来遍历树
在遍历过程中，记录每个节点收到通知的时间 cost，并且更新每个子节点的 cost 值。最后取所有叶子节点中最大的 cost 值即为所需时间。
具体实现过程如下：
- 使用邻接表存储树的结构；
- 从总负责人开始深度/广度优先遍历整棵树，在遍历过程中记录每个节点的 cost 值；
- 遍历每个节点的子节点，更新子节点的 cost 值为父节点的 cost 加上传递消息所需的时间 informTime；
- 在遍历结束时，统计所有叶子节点的 cost 值并返回其中的最大值。
时间复杂度：O(n)，其中 n 是员工数量，需要遍历所有员工。
具体实现代码如下：
①：使用深度优先搜索（DFS）来遍历树
import java.util.*;
class Solution {
private List<List<Integer>> graph;
private int result;
public int numOfMinutes(int n, int headID, int[] manager, int[] informTime) {
// 构建邻接表表示树
graph = new ArrayList<>();
for (int i = 0; i < n; i++) {
graph.add(new ArrayList<>());
}
for (int i = 0; i < n; i++) {
if (manager[i] != -1) {
graph.get(manager[i]).add(i);
}
}
// DFS 遍历树，并记录每个节点收到通知的时间 cost
result = 0;
dfs(headID, informTime[headID]);
return result;
}
private void dfs(int u, int cost) {
result = Math.max(result, cost);
for (int v : graph.get(u)) {
dfs(v, cost + informTime[v]);
}
}
}这里使用递归实现 DFS 遍历树，并记录每个节点收到通知的时间 cost。遍历结束后，统计所有叶子节点的 cost 值并返回其中的最大值。
需要注意的是，在每层递归中需要更新 cost 值为父节点的 cost 加上从父节点到当前节点所需的时间 informTime[u]。
②：可以使用广度优先搜索（BFS）来遍历树
import java.util.*;
class Solution {
public int numOfMinutes(int n, int headID, int[] manager, int[] informTime) {
// 构建邻接表表示树
List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i < n; i++) {
graph.add(new ArrayList<>());
}
for (int i = 0; i < n; i++) {
if (manager[i] != -1) {
graph.get(manager[i]).add(i);
}
}
// BFS 遍历树，并记录每个节点收到通知的时间 cost
int result = 0;
Queue<int[]> queue = new LinkedList<>();
queue.offer(new int[]{headID, 0});
while (!queue.isEmpty()) {
int[] node = queue.poll();
result = Math.max(result, node[1]);
for (int child : graph.get(node[0])) {
queue.offer(new int[]{child, node[1] + informTime[node[0]]});
}
}
return result;
}
}这里用到了 Java 中内置的队列实现——LinkedList，并且根据题目要求使用最后一个叶子节点的时间作为整个过程所需时间。
验证：返回力扣答题页面，运行代码测试（如下图）
可以看到成功运行，提交即可！
2023/05/01-23点46分 ，今日打卡成功！