题目大意：
收集树上所有苹果的最少时间
给你一棵有 n 个节点的无向树，节点编号为 0 到 n-1 ，它们中有一些节点有苹果。通过树上的一条边，需要花费 1 秒钟。你从 节点 0 出发，请你返回最少需要多少秒，可以收集到所有苹果，并回到节点 0 。
无向树的边由 edges 给出，其中 edges[i] = [fromi, toi] ，表示有一条边连接 from 和 toi 。除此以外，还有一个布尔数组 hasApple ，其中 hasApple[i] = true 代表节点 i 有一个苹果，否则，节点 i 没有苹果。
示例 1：
输入：n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], hasApple = [false,false,true,false,true,true,false] 输出：8 解释：上图展示了给定的树，其中红色节点表示有苹果。一个能收集到所有苹果的最优方案由绿色箭头表示。
示例 2：
输入：n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], hasApple = [false,false,true,false,false,true,false] 输出：6 解释：上图展示了给定的树，其中红色节点表示有苹果。一个能收集到所有苹果的最优方案由绿色箭头表示。
示例 3：
输入：n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], hasApple = [false,false,false,false,false,false,false]
输出：0
提示：
- 1 <= n <= 10^5
- edges.length == n-1
- edges[i].length == 2
- 0 <= fromi, toi <= n-1
- fromi < toi
- hasApple.length == n
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1443
解题思路分析：
leetcode中大部分题目都是有套路的，如果你不能找到套路解决它，就会被题目套路。对于树结构的题目，多数需要采用dfs或者bfs来解题。对于本题，我们使用dfs更加方便。
解题时，我们从顶点0开始向下做dfs递归处理，目的是遍历到每一个节点。本题的核心逻辑在于，除了顶点以外的所有节点，如果当前节点是苹果的话，那么为了保证收集到该苹果，一定需要从其父节点到达该节点，并且还需要从当前节点返回其父节点，这样一来一回需要耗时2个时间单位。另外，如果当前节点不是苹果，但是其子节点中包含苹果，这种情况下，为了到达其子节点，一定会经过当前节点，接下来再从其子节点返回到根节点时还会再次经过当前节点，因此该情况下当前节点也会消耗2个时间单位。
总结一下递归中的逻辑：
- 如果当前节点不是根节点，并且当前节点是苹果的话，返回子问题结果和再加上2。
- 如果当前节点不是根节点，并且当前节点子节点中包含苹果（子问题结果大于0），返回子问题结果和再加上2。
- 如果当前节点是跟节点，返回子问题结果和。
- 递归的终止条件是叶子节点。
实现代码：
public int minTime(int n, int[][] edges, List<Boolean> hasApple) {
// 转化为树形结构
Map<Integer,List<Integer>> map = new HashMap<>();
for(int[] edge : edges){
List<Integer> list = map.getOrDefault(edge[0],new ArrayList<>());
list.add(edge[1]);
map.put(edge[0],list);
}
// 递归求解
return dfs(map,hasApple,0);
}
int dfs(Map<Integer,List<Integer>> map, List<Boolean> hasApple, int node){
// 取得当前节点的所有子节点
List<Integer> list = map.get(node);
// 如果子节点为空（当前是叶子节点），如果当前是苹果返回2，反之返回0
if(list==null) return hasApple.get(node) ? 2: 0;
// 返回结果
int res=0;
// 遍历每个子节点
for(int child : list){
// 累加子问题的和
res+=dfs(map,hasApple,child);
}
// 如果当前不是根节点并且当前节点是苹果，或者子节点中包含苹果，结果再加2
if((res>0||hasApple.get(node))&&node!=0) res+=2;
return res;
}本题解法执行时间27ms。
Runtime: 27 ms, faster than 100.00% of Java online submissions for Minimum Time to Collect All Apples in a Tree.
Memory Usage: 80.6 MB, less than 100.00% of Java online submissions for Minimum Time to Collect All Apples in a Tree.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-1443-minimum-time-to-collect-all-apples-in-a-tree-解题思路分析/