X

LEETCODE 1443. Minimum Time to Collect All Apples in a Tree 解题思路分析

题目大意:

收集树上所有苹果的最少时间

给你一棵有 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个时间单位。

总结一下递归中的逻辑:

  1. 如果当前节点不是根节点,并且当前节点是苹果的话,返回子问题结果和再加上2。
  2. 如果当前节点不是根节点,并且当前节点子节点中包含苹果(子问题结果大于0),返回子问题结果和再加上2。
  3. 如果当前节点是跟节点,返回子问题结果和。
  4. 递归的终止条件是叶子节点。

实现代码:

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-解题思路分析/
Categories: leetcode
kwantong: