Medium

题目描述

给定一个由 n 个节点组成的无向树，节点编号从 0 到 n-1，其中一些节点上有苹果。你需要花费 1 秒时间走过树的一条边。返回从节点 0 出发并回到节点 0，收集树中所有苹果所需的最短时间（以秒为单位）。

无向树的边在数组 edges 中给出，其中 edges[i] = [ai, bi] 表示存在一条连接节点 ai 和 bi 的边。此外，还有一个布尔数组 hasApple，其中 hasApple[i] = true 表示节点 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 <= ai < bi <= n - 1
  • hasApple.length == n

提示：

  • 如果节点 u 包含苹果，那么从根节点到节点 u 路径上的所有边都必须往返使用（2次）。
  • 因此使用深度优先搜索（DFS）来检查一条边是否会被使用。

解题思路

解题思路

这是一个树上的DFS问题。核心思想是：只有当子树中存在苹果时，我们才需要访问该子树。

主要思路

  1. 建图：根据edges构建邻接表表示的无向树
  2. DFS遍历：从根节点0开始进行深度优先搜索
  3. 递归判断：对于每个节点，判断其子树是否需要访问
    • 如果当前节点有苹果，则必须访问
    • 如果当前节点的任一子树需要访问，则当前节点也需要访问
  4. 计算时间：每条需要走的边都要往返，所以每条边贡献2秒

关键洞察

  • 一条边会被使用当且仅当它连接的子树中有苹果
  • 每条被使用的边都需要往返，所以时间代价是边数×2
  • 使用DFS可以自底向上地判断每个子树是否需要访问

算法流程

  1. 构建邻接表
  2. 从节点0开始DFS
  3. 对于每个节点，递归检查所有子节点
  4. 如果子节点的子树需要访问，则当前边被使用，时间+2
  5. 返回当前子树是否需要访问（有苹果或子树有苹果）

代码实现

class Solution {
public:
    int minTime(int n, vector<vector<int>>& edges, vector<bool>& hasApple) {
        vector<vector<int>> graph(n);
        for (auto& edge : edges) {
            graph[edge[0]].push_back(edge[1]);
            graph[edge[1]].push_back(edge[0]);
        }
        
        return dfs(0, -1, graph, hasApple);
    }
    
private:
    int dfs(int node, int parent, vector<vector<int>>& graph, vector<bool>& hasApple) {
        int time = 0;
        
        for (int child : graph[node]) {
            if (child != parent) {
                int childTime = dfs(child, node, graph, hasApple);
                if (childTime > 0 || hasApple[child]) {
                    time += 2 + childTime;
                }
            }
        }
        
        return time;
    }
};

class Solution:
    def minTime(self, n: int, edges: List[List[int]], hasApple: List[bool]) -> int:
        graph = [[] for _ in range(n)]
        for a, b in edges:
            graph[a].append(b)
            graph[b].append(a)
        
        def dfs(node, parent):
            time = 0
            
            for child in graph[node]:
                if child != parent:
                    child_time = dfs(child, node)
                    if child_time > 0 or hasApple[child]:
                        time += 2 + child_time
            
            return time
        
        return dfs(0, -1)

public class Solution {
    public int MinTime(int n, int[][] edges, IList<bool> hasApple) {
        var graph = new List<int>[n];
        for (int i = 0; i < n; i++) {
            graph[i] = new List<int>();
        }
        
        foreach (var edge in edges) {
            graph[edge[0]].Add(edge[1]);
            graph[edge[1]].Add(edge[0]);
        }
        
        return Dfs(0, -1, graph, hasApple);
    }
    
    private int Dfs(int node, int parent, List<int>[] graph, IList<bool> hasApple) {
        int time = 0;
        
        foreach (int child in graph[node]) {
            if (child != parent) {
                int childTime = Dfs(child, node, graph, hasApple);
                if (childTime > 0 || hasApple[child]) {
                    time += 2 + childTime;
                }
            }
        }
        
        return time;
    }
}

var minTime = function(n, edges, hasApple) {
    const graph = Array.from({ length: n }, () => []);
    for (const [a, b] of edges) {
        graph[a].push(b);
        graph[b].push(a);
    }
    
    function dfs(node, parent) {
        let time = 0;
        
        for (const child of graph[node]) {
            if (child !== parent) {
                const childTime = dfs(child, node);
                if (childTime > 0 || hasApple[child]) {
                    time += 2 + childTime;
                }
            }
        }
        
        return time;
    }
    
    return dfs(0, -1);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)每个节点访问一次，每条边访问两次
空间复杂度O(n)邻接表存储图结构，递归调用栈深度最大为n