题目简介
有一棵根节点为 0 的家族树 ，总共包含 n 个节点，节点编号为 0 到 n – 1 。给你一个下标从 0 开始的整数数组 parents ，其中 parents[i] 是节点 i 的父节点。由于节点 0 是 根 ，所以 parents[0] == -1 。
总共有 $10^5$ 个基因值，每个基因值都用 闭区间 $[1, 10^5]$ 中的一个整数表示。给你一个下标从 0 开始的整数数组 nums ，其中 nums[i] 是节点 i 的基因值，且基因值互不相同 。
请你返回一个数组 ans ，长度为 n ，其中 ans[i] 是以节点 i 为根的子树内 缺失 的 最小 基因值。
节点 x 为根的 子树 包含节点 x 和它所有的后代节点。
思路
- 在概念上与41. 缺失的第一个正数题类似,都是找数,由于本题没有要求O(1)O(1)O(1)的空间复杂度,所以用哈希表是可能的
- 与数组中缺失的第一个正数类似的是,如果一棵树的节点不包括1,则以该树的任意节点为根的的子树都缺少1,这是最简单的情况
- 对于子节点有1的才是重要讨论的情况
解题方法
- 注意到需要处理的只是根节点到基因值为1的这一段的每个节点
- 注意到此时讨论的只是一条链
- 其他的节点的缺失值一定为1
- 可以用哈希表记录以该节点为根的子树包含的所有基因值,然后再每个节点都遍历一下
- 上述复杂度很高,再仔细观察节点的哈希表的形式,可以知道父节点的哈希表是所有子节点的合集加上自己的基因数
- 所以我们只需要自底向上遍历,维护一个哈希表就可以了
- 注意到父节点缺失的值不可能比子树缺失的还小,所以也需要维护一个基因数
- 时间复杂度:$O(n)$
- 空间复杂度:$O(n)$
代码
class Solution:
def smallestMissingValueSubtree(self, parents: List[int], nums: List[int]) -> List[int]:
n=len(parents)
res=[1]*n #默认最有可能缺1
if 1 not in nums:
return res
graph=[[]for _ in range(n)]
for i in range(1,n):
graph[parents[i]].append(i)
visited=set()
def dfs(index):
visited.add(nums[index])
for child in graph[index]:
if nums[child] not in visited:
dfs(child)
root=nums.index(1) #找分界点
now=2
while root>=0: #自底向上递归查找
dfs(root)
while now in visited:
now+=1
res[root]=now
root=parents[root]
return res</code></pre>
其他
这个理论上不能用与41题类似的将数组本身化为哈希表的操作,不然代码的复杂性很高,而且也不好理解