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

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

• 2≤n≤105
• 0≤father[i]<n,father[0]=−1
• 1≤times[i]≤1000,time[0]=−1

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

样例1
输入:
[-1,0,0]
[-1,3,5]
输出: 
5
解释:
这棵树如下所示：
   0
 3/\5
1    2
从0到1需要花费3个单位时间，从0到2需要花费5个单位时间，因此花费5个单位时间可以让水流到所有节点上。

        

          
        
        
        

          

          AI 代码解读
        
      
      

解题思路
从根节点向下 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 < n; i++){
            G.add(new ArrayList<Integer>());
        }
        for (int i = 1; i < n; 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;
    }
}

        

          
        
        
        

          

          AI 代码解读
        
      
      

更多题解参考：九章官网solution