[leetcode/lintcode 题解] 算法面试真题详解：给树浇水的时间

描述
有一棵n个节点的树，节点编号是0至n?1，其中0号节点是根节点，i号节点的父亲节点是father[i]。现在要对树浇水，把水撒到根节点上，水会顺着每一条边流下去，从i号节点的父亲流到i号节点需要time[i]的时间，请问需要多久水才能流到所有节点上。

2≤n≤1050≤father[i] n,father[0]=?11≤times[i]≤1000,time[0]=?1

在线评测地址：领扣题库官网

样例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
本站部分内容转载于网络，版权归原作者所有，转载之目的在于传播更多优秀技术内容，如有侵权请联系QQ/微信：153890879删除，谢谢！