这是一个关于树（Tree）和深度优先搜索（DFS）的经典算法题。

题目解析

核心目标：对于树中的每一个节点，找出其子树中缺失的最小正整数基因值。

关键观察（解题突破口）：
1.  如果一棵子树不包含基因值 1，那么它缺失的最小基因值一定是 1。
2.  只有包含基因值 1 的子树，其缺失的最小基因值才可能大于 1（比如 2, 3...）。
3.  因为基因值是唯一的，所以只有一个节点的基因值为 1。
4.  这意味着，我们只需要关注从基因值为 1 的节点一直到根节点的路径上的这些节点。路径之外的所有节点，答案直接就是 1。

算法思路

1.  初始化：创建一个结果数组 ans，将所有值初始化为 1。
2.  寻找起点：找到基因值为 1 的节点。如果找不到，直接返回全 1 的数组。
3.  向上遍历：从基因值为 1 的节点开始，沿着父节点一直向上遍历到根节点。
4.  收集基因值 (DFS)：对于路径上的每一个节点，使用 DFS 遍历它的整棵子树，将遇到的所有基因值加入到一个集合（Set）中。为了避免重复遍历，可以使用一个访问标记数组。
5.  计算 MEX (Minimum Excluded Value)：维护一个变量 mex（当前缺失的最小值）。每当我们向集合中加入新的基因值后，检查 mex 是否在集合中。如果在，mex 加 1，直到找到一个不在集合中的数。这个数就是当前子树的答案。

C语言实现

include 
include 
include 
include 

// 定义邻接表节点结构
typedef struct Node {
    int val;
    struct Node* next;
} Node;

// 全局变量用于DFS
int* g_nums;
bool* g_visited; // 记录节点是否被访问过，防止重复计算
bool* g_gene_set; // 记录基因值是否存在
int g_mex; // 当前缺失的最小基因值

// 深度优先搜索：收集子树中的所有基因值
void dfs(int node, Node** children) {
    if (g_visited[node]) return; // 如果已经访问过，直接返回
    
    g_visited[node] = true;
    
    // 将当前节点的基因值加入集合
    int gene_val = g_nums[node];
    g_gene_set[gene_val] = true;
    
    // 递归访问所有子节点
    Node* curr = children[node];
    while (curr != NULL) {
        dfs(curr->val, children);
        curr = curr->next;
    }
}

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* smallestMissingValueSubtree(int* parents, int parentsSize, int* nums, int numsSize, int* returnSize) {
    *returnSize = numsSize;
    g_nums = nums;
    
    // 1. 初始化结果数组，默认全为 1
    int* ans = (int*)malloc(sizeof(int) * numsSize);
    for (int i = 0; i val = i;
        new_node->next = children[parent_idx];
        children[parent_idx] = new_node;
    }
    
    // 4. 准备辅助数组
    g_visited = (bool*)calloc(numsSize, sizeof(bool)); // 节点访问标记
    // 基因值最大可能是 10^5，稍微开大一点防止越界
    g_gene_set = (bool*)calloc(100002, sizeof(bool)); 
    g_mex = 1; // 最小缺失值从 1 开始找
    
    // 5. 从基因值为 1 的节点开始，沿父节点路径向上遍历
    int curr_node = node_with_one;
    
    while (curr_node != -1) {
        // 对当前节点的子树进行 DFS，收集基因值
        dfs(curr_node, children);
        
        // 更新 mex
        while (g_gene_set[g_mex]) {
            g_mex++;
        }
        
        // 记录当前节点的答案
        ans[curr_node] = g_mex;
        
        // 移动到父节点
        curr_node = parents[curr_node];
    }
    
    // 6. 释放内存 (邻接表和辅助数组)
    for (int i = 0; i next;
            free(temp);
        }
    }
    free(children);
    free(g_visited);
    free(g_gene_set);
    
    return ans;
}

代码详解

1.  数据结构：
    *   children：使用邻接表（数组+链表）来存储树的结构，方便通过父节点快速找到所有子节点进行 DFS。
    *   g_gene_set：布尔数组，用来标记某个基因值是否已经出现过。
    *   g_visited：布尔数组，标记某个节点是否已经被处理过。这是优化的关键，避免在向上遍历时重复进入同一个子树分支。

2.  主逻辑 (smallestMissingValueSubtree)：
    *   首先假设所有答案都是 1。
    *   找到 nums[i] == 1 的位置。如果不存在，任务结束。
    *   如果存在，从该节点开始，利用 parents 数组不断向上找父节点，形成一条“关键路径”。

3.  DFS 过程：
    *   对于路径上的每个节点，调用 dfs。
    *   dfs 会遍历该节点下的所有后代，将它们的基因值标记在 g_gene_set 中。
    *   由于 g_visited 的存在，如果一个子树之前已经被父节点（更下方的节点）遍历过了，就不会再次进入，保证了时间复杂度接近 O(N)。

4.  计算答案：
    *   每次 DFS 结束后，检查 g_mex。只要 g_gene_set[g_mex] 为真，说明这个数存在，g_mex 自增。
    *   最终 g_mex 就是当前子树缺失的最小值。

复杂度分析

*   时间复杂度: O(N)。虽然看起来有循环和递归，但每个节点最多只会被 dfs 访问一次（由 g_visited 保证）。mex 变量在整个过程中只会增加，最多增加到 N+1，所以总的操作次数是线性的。
*   空间复杂度: O(N)。用于存储邻接表、访问标记数组和递归栈空间。