每棵子树内缺失的最小基因值

标签: 树 深度优先搜索 并查集 动态规划

难度: Hard

有一棵根节点为 0 的 家族树 ，总共包含 n 个节点，节点编号为 0 到 n - 1 。给你一个下标从 0 开始的整数数组 parents ，其中 parents[i] 是节点 i 的父节点。由于节点 0 是 根 ，所以 parents[0] == -1 。

总共有 105 个基因值，每个基因值都用 闭区间 [1, 105] 中的一个整数表示。给你一个下标从 0 开始的整数数组 nums ，其中 nums[i] 是节点 i 的基因值，且基因值 互不相同 。

请你返回一个数组 ans ，长度为 n ，其中 ans[i] 是以节点 i 为根的子树内 缺失 的 最小 基因值。

节点 x 为根的 子树 包含节点 x 和它所有的 后代 节点。

示例 1：

输入：parents = [-1,0,0,2], nums = [1,2,3,4]
输出：[5,1,1,1]
解释：每个子树答案计算结果如下：
- 0：子树包含节点 [0,1,2,3] ，基因值分别为 [1,2,3,4] 。5 是缺失的最小基因值。
- 1：子树只包含节点 1 ，基因值为 2 。1 是缺失的最小基因值。
- 2：子树包含节点 [2,3] ，基因值分别为 [3,4] 。1 是缺失的最小基因值。
- 3：子树只包含节点 3 ，基因值为 4 。1是缺失的最小基因值。

示例 2：

输入：parents = [-1,0,1,0,3,3], nums = [5,4,6,2,1,3]
输出：[7,1,1,4,2,1]
解释：每个子树答案计算结果如下：
- 0：子树内包含节点 [0,1,2,3,4,5] ，基因值分别为 [5,4,6,2,1,3] 。7 是缺失的最小基因值。
- 1：子树内包含节点 [1,2] ，基因值分别为 [4,6] 。 1 是缺失的最小基因值。
- 2：子树内只包含节点 2 ，基因值为 6 。1 是缺失的最小基因值。
- 3：子树内包含节点 [3,4,5] ，基因值分别为 [2,1,3] 。4 是缺失的最小基因值。
- 4：子树内只包含节点 4 ，基因值为 1 。2 是缺失的最小基因值。
- 5：子树内只包含节点 5 ，基因值为 3 。1 是缺失的最小基因值。

示例 3：

输入：parents = [-1,2,3,0,2,4,1], nums = [2,3,4,5,6,7,8]
输出：[1,1,1,1,1,1,1]
解释：所有子树都缺失基因值 1 。

提示：

  • n == parents.length == nums.length
  • 2 <= n <= 105
  • 对于 i != 0 ，满足 0 <= parents[i] <= n - 1
  • parents[0] == -1
  • parents 表示一棵合法的树。
  • 1 <= nums[i] <= 105
  • nums[i] 互不相同。

Submission

运行时间: 252 ms

内存: 50.1 MB

class Solution:
    def smallestMissingValueSubtree(self, parents: List[int], nums: List[int]) -> List[int]:
        n = len(nums)
        if min(nums)!=1: return [1]*n
        idx = nums.index(1)
        g = [[] for _ in range(n)]
        for i in range(1, n):
            g[parents[i]].append(i)
        ans = [1] * n
        vis = set()
        mn = 2
        son = -1
        while idx >= 0:
            vis.add(nums[idx])
            st = [i for i in g[idx] if i!=son]
            while st:
                cur = st.pop()
                vis.add(nums[cur]) 
                st.extend(g[cur])
            while mn in vis: mn += 1
            son = idx
            ans[idx] = mn
            idx = parents[idx]
        return ans

Explain

此题解采用的是一种高效的方法，首先检查基因值是否包含1，因为如果不包含1，则所有子树的最小缺失基因值必定是1。如果包含1，我们需要找到包含基因值1的节点，并采用从该节点向根节点追溯的方式，逐一查找每个节点所在子树的最小缺失基因值。使用DFS (深度优先搜索) 遍历节点，将访问过的基因值存入集合中，并实时更新未见的最小基因值。这种方法只需要处理包含1的节点到根节点路径上的子树，其他节点的答案直接是1，因此效率较高。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def smallestMissingValueSubtree(self, parents: List[int], nums: List[int]) -> List[int]:
        n = len(nums)
        # 如果没有基因值1，则所有子树的最小缺失值为1
        if min(nums) != 1: return [1] * n
        # 找到基因值为1的节点的索引
        idx = nums.index(1)
        # 构建图，用于存储树中的父子关系
        g = [[] for _ in range(n)]
        for i in range(1, n):
            g[parents[i]].append(i)
        # 初始化答案数组，所有值设为1（最小可能缺失的基因值）
        ans = [1] * n
        # 创建一个集合来存储访问过的基因值
        vis = set()
        # 初始化最小缺失值为2（因为1已存在）
        mn = 2
        son = -1
        # 从包含基因值1的节点开始，向上遍历到根节点
        while idx >= 0:
            vis.add(nums[idx])
            # 获取当前节点的所有子节点，除了来时的节点
            st = [i for i in g[idx] if i != son]
            # DFS遍历子树，收集所有基因值
            while st:
                cur = st.pop()
                vis.add(nums[cur])
                st.extend(g[cur])
            # 更新最小缺失的基因值
            while mn in vis: mn += 1
            # 向上移动到父节点，继续检查
            son = idx
            ans[idx] = mn
            idx = parents[idx]
        return ans

Explore

是的，您的理解是正确的。在题解中，算法首先检查基因值是否包含1，因为1是最小的基因值，如果树中任何节点都没有基因值1，则每个节点的最小缺失基因值必然是1（因为基因值从1开始且是连续的）。如果树中的任一节点包含基因值1，则我们需要特别关注这个节点及其所有祖先节点，因为这些节点的子树可能包含从1开始的连续基因值序列，从而影响最小缺失基因值的计算。因此，只有当基因值1存在时，我们才需要对包含这个基因值的节点及其祖先节点进行更复杂的最小缺失基因值搜索。

在此题解中选择DFS而不是BFS主要是由于DFS的递归特性使得我们能够更方便地在遍历过程中处理和更新节点的状态。在遍历并收集基因值时，DFS允许我们自然地跟踪节点的访问路径，并且在回溯阶段可以方便地更新节点的状态，这在处理树结构数据时非常有用。相比之下，BFS会同时处理同一层级的所有节点，这在需要频繁更新节点状态或依赖节点遍历路径的情况下可能不太方便。在此算法中，我们需要从包含基因值1的节点开始向根节点逐级检查和更新最小缺失基因值，DFS的深入优先特性更符合这一需求。

在这个问题中，我们的主要目的是能够从任一节点向下访问其所有子节点。这是因为算法的核心在于从包含基因值1的节点出发，向下遍历其所有子树以收集和更新基因值信息。因此，构建图时主要记录每个节点的子节点，这样可以直接从任一节点访问其所有直接子节点。如果同时记录父节点的索引，则会增加额外的存储需求和管理复杂性，而在本题中，父节点信息已通过题目给定的'parents'数组直接提供，无需通过图结构再次记录。因此，仅记录子节点的索引简化了数据结构的管理，同时足以支持题目要求的遍历和操作，提高了算法的效率。