题目地址：

https://www.lintcode.com/problem/time-to-flower-tree/description

给定一棵$n$个节点的树，节点编号$0\sim n-1$，$0$是根节点。给定一个数组$A$代表从每个节点的父节点到该节点的路径长度。问从根节点到哪个叶子节点的路径最长。返回最长距离。

思路是DFS。但这里需要用栈模拟DFS，直接DFS容易递归层数太深。代码如下：

import java.util.*; public class Solution { class Pair { int idx, time; public Pair(int idx, int time) { this.idx = idx; this.time = time; } } /** * @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 // 邻接表建图 Map<Integer, List<Integer>> tree = buildTree(father); Deque<Pair> stack = new ArrayDeque<>(); stack.push(new Pair(0, 0)); int res = 0; while (!stack.isEmpty()) { Pair cur = stack.pop(); // 如果cur.idx不存在，说明走到叶子了，更新时间 if (!tree.containsKey(cur.idx)) { res = Math.max(res, cur.time); } else { for (int next : tree.get(cur.idx)) { stack.push(new Pair(next, cur.time + time[next])); } } } return res; } private Map<Integer, List<Integer>> buildTree(int[] father) { Map<Integer, List<Integer>> tree = new HashMap<>(); tree.put(0, new ArrayList<>()); for (int i = 1; i < father.length; i++) { tree.putIfAbsent(father[i], new ArrayList<>()); tree.get(father[i]).add(i); } return tree; } }

时空复杂度$O(V)$。