Leetcode 1443. 收集树上所有苹果的最少时间(无向树上的DFS)

问题描述

给你一棵有 n 个节点的无向树，节点编号为 0 到 n-1 ，它们中有一些节点有苹果。通过树上的一条边，需要花费 1 秒钟。你从 节点 0 出发，请你返回最少需要多少秒，可以收集到所有苹果，并回到节点 0 。

无向树的边由 edges 给出，其中 edges[i] = [fromi, toi] ，表示有一条边连接 from 和 toi 。除此以外，还有一个布尔数组 hasApple ，其中 hasApple[i] = true 代表节点 i 有一个苹果，否则，节点 i 没有苹果。

Example

示例 1：

输入：n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], hasApple = [false,false,true,false,false,true,false]

输出：6

解释：上图展示了给定的树，其中红色节点表示有苹果。一个能收集到所有苹果的最优方案由绿色箭头表示。

示例 2：

输入：n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], hasApple = [false,false,false,false,false,false,false]

输出：0

题目链接：1443. 收集树上所有苹果的最少时间 (难度:中等)

思路

从题目的描述中可以看出，这其实是一个无向图上的搜索问题。显然从示范用例当中可以看出两个特例：

• 如果苹果的个数为 0，则收集次数为 0 次

• 如果苹果个数为 n，则显然收集次数应当为 2 * (n - 1)

  因此，我们需要先对无向树建立邻接表，并统计苹果的个数。当苹果个数 x 满足 0 < x < n 时，我们采用深度优先搜索的方式，搜索策略如下：

设 dfs(root, graph, hasApple, visited) 为收集根为 root 的树上的苹果所需要的最少次数

• 若 root 为叶节点，则判断 root 上是否有苹果。若有，则返回 2，若没有，则返回 0；【从父节点出发去子节点摘苹果并返回，同一条边需要走两次】
• 若 root 非叶节点，则访问所有与 root 相邻的节点，并统计它们的最少收集次数 ans。若 ans = 0，则看 root 节点上是否有苹果，有的话返回 2， 没有返回 0；

代码

class Solution {
public:
    int dfs(int root, vector<vector<int>>& graph, vector<bool>& hasApple,vector<bool>& visited){
        int ans = 0;
        visited[root] = true;
        for(int i = 0;i < graph[root].size();++i){
            if(visited[graph[root][i]])  continue;
            ans += dfs(graph[root][i], graph, hasApple,visited);
        }
        if(ans == 0){
            return hasApple[root] ? 2 : 0;
        }
        return ans + 2;
    }
    int minTime(int n, vector<vector<int>>& edges, vector<bool>& hasApple) {
        vector<vector<int>> graph(n,vector<int>{});
        vector<bool> visited(n, false);
        int cnt = 0;
        for(int i = 0;i < n - 1;++i){
            cnt += hasApple[i];
            graph[edges[i][0]].push_back(edges[i][1]);
            graph[edges[i][1]].push_back(edges[i][0]);
        }
        cnt += hasApple.back();
        if(cnt == 0){
            return 0;
        }else if(cnt == n){
            return (n - 1) * 2;
        }
        return dfs(0, graph, hasApple,visited) - 2;
    }
};

执行结果： 404 ms, 60.5 MB

赏

谢谢你请我吃糖果

支付宝

微信

• 本文作者： Phoenix
• 本文链接： https://phoenix500526.github.io/2020/06/24/Leetcode-1443-收集树上所有苹果的最少时间-无向树上的DFS/
• 版权声明： 本博客所有文章除特别声明外，均采用 MIT 许可协议。转载请注明出处！