2003. Smallest Missing Genetic Value in Each Subtree

DFS + TreeMap (TLE)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
class Solution {
    private static class TreeNode {
        private final int index;
        private final List<TreeNode> children;

        public TreeNode(int index) {
            this.index = index;
            this.children = new ArrayList<>();
        }
    }

    public int[] smallestMissingValueSubtree(int[] parents, int[] nums) {
        // 1. 建树
        TreeNode[] nodes = new TreeNode[parents.length];
        for (int i = 0; i < parents.length; i++) {
            TreeNode node = new TreeNode(i);
            nodes[i] = node;
        }

        for (int i = 1; i < parents.length; i++) {
            TreeNode node = nodes[i];
            TreeNode parentNode = nodes[parents[i]];
            parentNode.children.add(node);
        }

        // 2. 自底向上 DFS
        int[] res = new int[parents.length];
        dfs(nodes[0], nums, res);
        return res;
    }

    private TreeSet<Integer> dfs(TreeNode node, int[] nums, int[] res) {
        if (node.children.isEmpty()) {
            TreeSet<Integer> treeSet = new TreeSet<>(); // 存储缺失的值，初始状态全部缺失
            for (int i = 1; i <= 100000; i++) {
                treeSet.add(i);
            }
            treeSet.remove(nums[node.index]); // 移除缺失的值
            res[node.index] = treeSet.higher(0);
            return treeSet;
        }

        List<TreeSet<Integer>> treeSetList = new ArrayList<>(node.children.size());
        for (int i = 0; i < node.children.size(); i++) {
            treeSetList.add(dfs(node.children.get(i), nums, res));
        }

        TreeSet<Integer> treeSet = treeSetList.get(0);
        for (int i = 1; i < treeSetList.size(); i++) {
            treeSet.retainAll(treeSetList.get(i));
        }

        treeSet.remove(nums[node.index]); // 移除缺失的值
        res[node.index] = treeSet.higher(0);

        return treeSet;
    }
}

DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
class Solution {
    public int[] smallestMissingValueSubtree(int[] parents, int[] nums) {
        int[] res = new int[parents.length];
        Arrays.fill(res, 1);

        int startNodeIndex = -1;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 1) {
                startNodeIndex = i;
                break;
            }
        }

        if (startNodeIndex == -1) {
            // 未找到基因值为 1 的节点，所有子树缺失的基因值均为 1, 直接返回
            return res;
        }

        List<List<Integer>> childrenList = new ArrayList<>(parents.length);
        for (int i = 0; i < parents.length; i++) {
            childrenList.add(new ArrayList<>());
        }

        for (int i = 1; i < parents.length; i++) { // 注意此处从索引 1 开始，否则根节点 -1 会导致越界
            childrenList.get(parents[i]).add(i);
        }

        Set<Integer> geneticValueSet = new HashSet<>();
        int missingGeneticValue = 2;
        int nodeIndex = startNodeIndex;
        while (nodeIndex != -1) {
            dfs(nodeIndex, childrenList, nums, geneticValueSet); // 遍历当前节点的子树
            while (geneticValueSet.contains(missingGeneticValue)) {
                missingGeneticValue++;
            }
            res[nodeIndex] = missingGeneticValue;
            nodeIndex = parents[nodeIndex]; // 跳转至父节点
        }

        return res;
    }

    private void dfs(int nodeIndex, List<List<Integer>> childrenList, int[] nums, Set<Integer> geneticValueSet) {
        geneticValueSet.add(nums[nodeIndex]);
        for (int childIndex : childrenList.get(nodeIndex)) {
            if (!geneticValueSet.contains(nums[childIndex])) { // 题目保证了每个节点的基因值不同
                dfs(childIndex, childrenList, nums, geneticValueSet);
            }
        }
    }
}

References

2003. Smallest Missing Genetic Value in Each Subtree