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

链接：2003.每棵子树内缺失的最小基因值
难度：Hard
标签：树、深度优先搜索、并查集、动态规划
简介：请你返回一个数组 ans ，长度为 n ，其中 ans[i] 是以节点 i 为根的子树内 缺失 的 最小 基因值。

题解 1 - python

• 编辑时间：2023-10-31
• 执行用时：812ms
• 内存消耗：172.67MB
• 编程语言：python
• 解法介绍：dfs时用set存储所有值。

class Solution:
    def smallestMissingValueSubtree(self, parents: List[int], nums: List[int]) -> List[int]:
        n = len(parents)
        nodes = [[] for i in range(n)]
        for i in range(1, n): nodes[parents[i]].append(i)
        ans = [1 for _ in range(n)]
        def dfs(idx: int) -> (int, Set[int]):
            last = 1
            s = set([nums[idx]])
            for child in nodes[idx]:
                resLast, resSet = dfs(child)
                last = max(last, resLast)
                if len(resSet) > len(s):
                    resSet |= s
                    s = resSet
                else:
                    s |= resSet
            while last in s: last += 1
            ans[idx] = last
            return last, s
        dfs(0)
        return ans

题解 2 - python

• 编辑时间：2023-10-31
• 执行用时：452ms
• 内存消耗：66.3MB
• 编程语言：python
• 解法介绍：自底向上，只遍历存在1的树。

class Solution:
    def smallestMissingValueSubtree(self, parents: List[int], nums: List[int]) -> List[int]:
        n = len(parents)
        nodes = [[] for i in range(n)]
        for i in range(1, n): nodes[parents[i]].append(i)
        ans = [1 for _ in range(n)]
        used = [False for _ in range(n)]
        s = set()
        def dfs(idx: int):
            if used[idx]: return
            used[idx] = True
            s.add(nums[idx])
            for child in nodes[idx]: dfs(child)
        
        cur = nums.index(1) if 1 in nums else -1
        last = 1
        while cur != -1:
            dfs(cur)
            while last in s: last += 1
            ans[cur] = last
            cur = parents[cur]
        return ans