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

难度: Medium

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

无向树的边由 edges 给出，其中 edges[i] = [from_i, to_i] ，表示有一条边连接 from 和 to_i 。除此以外，还有一个布尔数组 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 <= a_i < b_i <= n - 1
hasApple.length == n

Submission

运行时间: 104 ms

内存: 45.0 MB

class Solution:
    def minTime(self, n: int, edges: List[List[int]], hasApple: List[bool]) -> int:
        # 对于 叶子节点 如果 有苹果 那么返回时间为 2
        # 非叶子节点 ， 如果有苹果 返回时间 为 2 + 左子树的时间和右子树的时间

        def dfs(u: int, fa: int) -> int:
            # 如果是叶子节点
            if u != 0 and len(g[u]) == 1:
                return int(hasApple[u]) * 2
            res = 0
            for v in g[u]:
                if v != fa:
                    res += dfs(v, u)
            if res > 0:
                return res + (2 if u != 0 else 0)
            return int(hasApple[u]) * 2 if u != 0 else 0

        g = [[] for _ in range(n)]
        for u, v in edges:
            g[u].append(v)
            g[v].append(u)
        ans = dfs(0, -1)
        return ans

Explain

题解使用深度优先搜索（DFS）策略，递归地计算树中每个节点所需要的最小时间。基本思路是：从根节点（节点 0）开始，向下遍历每个节点，计算从该节点到其所有子节点收集苹果并返回所需的总时间。如果一个节点或其任何子节点有苹果，该节点返回的时间包括到子节点的往返时间（每个边2秒）。若叶子节点有苹果，则计算其到父节点的往返时间。若叶子节点无苹果，则不需要时间。对于根节点，只需要累加从根节点到其子节点的时间，因为不需要返回根节点。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def minTime(self, n: int, edges: List[List[int]], hasApple: List[bool]) -> int:
        # 构建图的邻接表
        g = [[] for _ in range(n)]
        for u, v in edges:
            g[u].append(v)
            g[v].append(u)
        # 定义深度优先搜索函数
        def dfs(u: int, fa: int) -> int:
            # 判断是否为叶子节点（除根节点外，连接数为1的节点）
            if u != 0 and len(g[u]) == 1:
                return int(hasApple[u]) * 2
            # 遍历所有子节点，累加时间
            res = 0
            for v in g[u]:
                if v != fa:
                    res += dfs(v, u)
            # 如果该节点或其子节点有苹果，累加往返时间
            if res > 0 or hasApple[u]:
                return res + (2 if u != 0 else 0)
            return 0
        # 开始从根节点进行DFS
        ans = dfs(0, -1)
        return ans

Explore

在深度优先搜索（DFS）中传递父节点编号`fa`是为了防止算法回溯到父节点，从而导致无限循环。由于图的邻接表表示中，每个节点都记录了与它相连的所有节点（包括父节点），如果不通过父节点编号来区分，递归调用时会重新访问父节点，造成重复计算和循环调用。传递父节点编号可以确保每次递归只处理当前节点的子节点，而不包括其父节点。

在DFS的实现中，通过传递当前节点的父节点编号`fa`并在每次递归中检查，确保不会向父节点方向递归，从而避免重复访问同一个节点。此外，在递归函数中，每次遍历子节点前会检查该子节点是否是来自父节点的调用，只有当子节点不是父节点时，才会对该子节点进行递归调用。这样就可以确保算法在遍历过程中每个节点只被访问一次，避免了无限循环的问题。

在递归的基案中，叶子节点定义为除根节点外只与一个节点（其父节点）相连的节点。当叶子节点有苹果时，需要计算从该叶子节点到其父节点的往返时间，因此返回`2`（每个边的往返时间为2秒）。使用`int(hasApple[u]) * 2`是为了根据叶子节点是否有苹果来决定返回的时间：若有苹果（`hasApple[u]`为`true`），则返回`2`；若无苹果（`hasApple[u]`为`false`），则返回`0`。这样的处理确保了只有含有苹果的叶子节点才贡献额外的往返时间。