leetcode.1376 通知所有员工所需的时间 - bfs/dfs + 树

1376. 通知所有员工所需的时间

目录

一、bfs 

 二、dfs

---

题目：

• 公司里有 n 名员工，每个员工的 ID 都是独一无二的，编号从 0 到 n - 1。
• 公司的总负责人通过 headID 进行标识。
• 在 manager 数组中，每个员工都有一个直属负责人，其中 manager[i] 是第 i 名员工的直属负责人。
• 对于总负责人，manager[headID] = -1。题目保证从属关系可以用树结构显示。
• 公司总负责人想要向公司所有员工通告一条紧急消息。他将会首先通知他的直属下属们，然后由这些下属通知他们的下属，直到所有的员工都得知这条紧急消息。
• 第 i 名员工需要 informTime[i] 分钟来通知它的所有直属下属（也就是说在 informTime[i] 分钟后，他的所有直属下属都可以开始传播这一消息）。
• 返回通知所有员工这一紧急消息所需要的 分钟数

一、bfs 

思路：

刚开始读错题了，以为是所有人都通知到的总时间

但这题其实是，返回通知到最深一层的时间，即求最深树权值之和

我们可以用bfs遍历整棵树，队列存二元组【节点值，当前路累计权值】

如果发现没有子节点，则更新最大值

否则遍历子节点，累加权值入队

class Solution {static int N=100010;int[] h=new int[N],e=new int[N],ne=new int[N];int idx;public void add(int a,int b){e[idx]=b;ne[idx]=h[a];h[a]=idx++;}public int numOfMinutes(int n, int headID, int[] manager, int[] informTime) {int res=informTime[headID];Arrays.fill(h,-1);for(int i=0;i<n;i++) {if(manager[i]==-1) continue;add(manager[i],i);}Queue<int[]> q=new LinkedList<>();q.offer(new int[]{headID,informTime[headID]});while(!q.isEmpty()){var t=q.poll();int id=t[0],val=t[1];if(h[id]==-1) {res=Math.max(res,val);continue;}for(int i=h[id];i!=-1;i=ne[i]){int j=e[i];q.offer(new int[]{j,val+informTime[j]});}}return res;}
}

 二、dfs

思路：

用dfs从根节点开始深入

计算每一个节点向下传递信息的最大值

class Solution {static int N=100010;int[] h=new int[N],e=new int[N],ne=new int[N];int idx;public void add(int a,int b){e[idx]=b;ne[idx]=h[a];h[a]=idx++;}public int dfs(int u,int[] informTime){int res=0;for(int i=h[u];i!=-1;i=ne[i]){int j=e[i];res=Math.max(res,dfs(j,informTime));}return informTime[u]+res;}public int numOfMinutes(int n, int headID, int[] manager, int[] informTime) {int res=informTime[headID];Arrays.fill(h,-1);for(int i=0;i<n;i++) {if(manager[i]==-1) continue;add(manager[i],i);}return dfs(headID,informTime);}
}