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

/*
 * 思路：
 * 1. 构建树的结构，使用一个邻接列表表示。
 * 2. 使用深度优先搜索（DFS）遍历每个节点的子树，并记录每个子树的基因值。
 * 3. 对于每个节点，找到其子树中缺失的最小基因值。
 */

import java.util.*;
import java.util.stream.*;

public class FamilyTreeStream {
    public int[] findMissingGenes(int[] parents, int[] nums) {
        int n = parents.length;
        List<Integer>[] tree = IntStream.range(0, n).mapToObj(i -> new ArrayList<Integer>()).toArray(ArrayList[]::new);
        IntStream.range(1, n).forEach(i -> tree[parents[i]].add(i));

        int[] result = new int[n];
        boolean[] seen = new boolean[100001];
        dfs(0, tree, nums, result, seen);
        return result;
    }

    private void dfs(int node, List<Integer>[] tree, int[] nums, int[] result, boolean[] seen) {
        Set<Integer> subtreeGenes = new HashSet<>();
        Stack<Integer> stack = new Stack<>();
        stack.push(node);
        while (!stack.isEmpty()) {
            int current = stack.pop();
            subtreeGenes.add(nums[current]);
            tree[current].forEach(stack::push);
        }

        result[node] = IntStream.range(1, 100001).filter(i -> !subtreeGenes.contains(i)).findFirst().orElse(100001);
    }

    public static void main(String[] args) {
        FamilyTreeStream ft = new FamilyTreeStream();
        int[] parents1 = {-1, 0, 0, 2};
        int[] nums1 = {1, 2, 3, 4};
        System.out.println(Arrays.toString(ft.findMissingGenes(parents1, nums1))); // [5, 1, 1, 1]
    }
}