Hard

题目描述

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

共有 10^5 个遗传值，每个遗传值用范围 [1, 10^5] 内的整数表示。给你一个下标从 0 开始的整数数组 nums，其中 nums[i] 是节点 i 的遗传值，且各不相同。

返回一个长度为 n 的数组 ans，其中 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]

示例 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 <= 10^5
  • 0 <= parents[i] <= n - 1 (i != 0 时)
  • parents[0] == -1
  • parents 表示一棵有效的树
  • 1 <= nums[i] <= 10^5
  • 每个 nums[i] 都不相同

解题思路

这道题的核心在于找到每个子树中缺失的最小正整数。我们可以通过以下观察来优化算法：

关键观察：

  1. 如果子树中不包含值1，那么答案必定是1
  2. 只有包含值1的子树，答案才可能大于1
  3. 从包含值1的节点开始，向根节点遍历，每个祖先节点的子树都包含值1

算法思路：

  1. 建图：根据parents数组构建邻接表表示的树
  2. 找到值为1的节点：这是我们需要特殊处理的起点
  3. 向上遍历路径：从值为1的节点开始，沿着父节点向根节点遍历
  4. 动态维护集合：对于路径上的每个节点，收集其子树中的所有值，并找到最小缺失值
  5. 优化：使用集合来快速查找缺失值，避免重复计算

具体实现：

  • 使用DFS收集子树中的所有遗传值
  • 对于不在"值1到根"路径上的节点，答案直接是1
  • 对于路径上的节点，维护一个包含子树所有值的集合，从1开始查找第一个缺失的正整数

时间复杂度主要来自于遍历树和维护集合操作。

代码实现

class Solution {
public:
    vector<int> smallestMissingValueSubtree(vector<int>& parents, vector<int>& nums) {
        int n = parents.size();
        vector<vector<int>> children(n);
        vector<int> ans(n, 1);
        
        // 建图
        for (int i = 1; i < n; i++) {
            children[parents[i]].push_back(i);
        }
        
        // 找到值为1的节点
        int nodeWith1 = -1;
        for (int i = 0; i < n; i++) {
            if (nums[i] == 1) {
                nodeWith1 = i;
                break;
            }
        }
        
        if (nodeWith1 == -1) return ans; // 没有值1，所有答案都是1
        
        unordered_set<int> visited;
        int missing = 1;
        
        // 从值为1的节点向根遍历
        while (nodeWith1 != -1) {
            dfs(nodeWith1, children, nums, visited);
            
            // 找到当前子树的最小缺失值
            while (visited.count(missing)) {
                missing++;
            }
            ans[nodeWith1] = missing;
            nodeWith1 = parents[nodeWith1];
        }
        
        return ans;
    }
    
private:
    void dfs(int node, vector<vector<int>>& children, vector<int>& nums, unordered_set<int>& visited) {
        visited.insert(nums[node]);
        for (int child : children[node]) {
            dfs(child, children, nums, visited);
        }
    }
};

class Solution:
    def smallestMissingValueSubtree(self, parents: List[int], nums: List[int]) -> List[int]:
        n = len(parents)
        children = [[] for _ in range(n)]
        ans = [1] * n
        
        # 建图
        for i in range(1, n):
            children[parents[i]].append(i)
        
        # 找到值为1的节点
        node_with_1 = -1
        for i in range(n):
            if nums[i] == 1:
                node_with_1 = i
                break
        
        if node_with_1 == -1:
            return ans  # 没有值1，所有答案都是1
        
        visited = set()
        missing = 1
        
        def dfs(node):
            visited.add(nums[node])
            for child in children[node]:
                dfs(child)
        
        # 从值为1的节点向根遍历
        while node_with_1 != -1:
            dfs(node_with_1)
            
            # 找到当前子树的最小缺失值
            while missing in visited:
                missing += 1
            ans[node_with_1] = missing
            node_with_1 = parents[node_with_1]
        
        return ans

public class Solution {
    public int[] SmallestMissingValueSubtree(int[] parents, int[] nums) {
        int n = parents.Length;
        List<int>[] children = new List<int>[n];
        int[] ans = new int[n];
        
        for (int i = 0; i < n; i++) {
            children[i] = new List<int>();
            ans[i] = 1;
        }
        
        // 建图
        for (int i = 1; i < n; i++) {
            children[parents[i]].Add(i);
        }
        
        // 找到值为1的节点
        int nodeWith1 = -1;
        for (int i = 0; i < n; i++) {
            if (nums[i] == 1) {
                nodeWith1 = i;
                break;
            }
        }
        
        if (nodeWith1 == -1) return ans; // 没有值1，所有答案都是1
        
        HashSet<int> visited = new HashSet<int>();
        int missing = 1;
        
        // 从值为1的节点向根遍历
        while (nodeWith1 != -1) {
            Dfs(nodeWith1, children, nums, visited);
            
            // 找到当前子树的最小缺失值
            while (visited.Contains(missing)) {
                missing++;
            }
            ans[nodeWith1] = missing;
            nodeWith1 = parents[nodeWith1];
        }
        
        return ans;
    }
    
    private void Dfs(int node, List<int>[] children, int[] nums, HashSet<int> visited) {
        visited.Add(nums[node]);
        foreach (int child in children[node]) {
            Dfs(child, children, nums, visited);
        }
    }
}

var smallestMissingValueSubtree = function(parents, nums) {
    const n = parents.length;
    const children = Array.from({length: n}, () => []);
    const ans = new Array(n).fill(1);
    
    // 建图
    for (let i = 1; i < n; i++) {
        children[parents[i]].push(i);
    }
    
    // 找到值为1的节点
    let nodeWith1 = -1;
    for (let i = 0; i < n; i++) {
        if (nums[i]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n) - 每个节点最多被访问一次，集合操作均摊O(1)
空间复杂度O(n) - 存储树结构和访问集合所需的空间