描述
有一棵n个节点的树,节点编号是0至n?1,其中0号节点是根节点,i号节点的父亲节点是father[i]。现在要对树浇水,把水撒到根节点上,水会顺着每一条边流下去,从i号节点的父亲流到i号节点需要time[i]的时间,请问需要多久水才能流到所有节点上。
在线评测地址:领扣题库官网
样例1 [-1,0,0] [-1,3,5] 这棵树如下所示: 3/\5 从0到1需要花费3个单位时间,从0到2需要花费5个单位时间,因此花费5个单位时间可以让水流到所有节点上。
解题思路
从根节点向下 bfs,每次记录时间即可。
public class Solution { * @param father: the father of every node * @param time: the time from father[i] to node i * @return: time to flower tree public int timeToFlowerTree(int[] father, int[] time) { // write your code here int n = father.length; //ArrayList G[] = new ArrayList[n]; ArrayList ArrayList Integer G= new ArrayList ArrayList Integer (); for (int i = 0; i i++){ G.add(new ArrayList Integer for (int i = 1; i i++){ G.get(father[i]).add(i); int maxx = 0; Queue Integer eqnode = new LinkedList Integer Queue Integer eqtime = new LinkedList Integer eqnode.offer(0); eqtime.offer(0); while (!eqnode.isEmpty()){ int curnode = eqnode.poll(); int curtime = eqtime.poll(); maxx = Math.max(maxx, curtime); for (int v: G.get(curnode)){ eqnode.offer(v); eqtime.offer(curtime + time[v]); return maxx; }
更多题解参考:九章官网solution
本文转自网络,原文链接:https://developer.aliyun.com/article/783406