👍Runtime 54 ms Beats 90.32%
Code\n\nclass Solution {\n    public int[] smallestMissingValueSubtree(int[] parents, int[] nums) {\n        int n = parents.length;\n        List<List<Integer>
# Code\n```\nclass Solution {\n    public int[] smallestMissingValueSubtree(int[] parents, int[] nums) {\n        int n = parents.length;\n        List<List<Integer>> tree = new ArrayList<>();\n        for (int i = 0; i < n; i++) {\n            tree.add(new ArrayList<>());\n        }\n        for (int i = 1; i < n; i++) {\n            tree.get(parents[i]).add(i); // build the tree\n        }\n\n        int[] ans = new int[n];\n        Arrays.fill(ans, 1);\n        int k = -1;\n        for (int i = 0; i < n; i++) {\n            if (nums[i] == 1) {\n                k = i;\n                break;\n            }\n        }\n        if (k == -1) return ans; // check whether 1 exists in nums\n\n        boolean[] visitedGeneSet = new boolean[100002]; // used to find current minimum unvisited gene\n        int doNotVisit = -1; // index we no longer need to visit because it has been visited in the previous while loop\n        int curMin = 1;\n\n        while (k != -1) { // while there is still a node unvisited in path (gene:1 -> root)\n            Queue<Integer> queue = new LinkedList<>();\n            queue.add(k); // start BFS from that node\n            while (!queue.isEmpty()) {\n                int front = queue.poll();\n                visitedGeneSet[nums[front]] = true;\n                for (int child : tree.get(front)) {\n                    if (child != doNotVisit) queue.add(child); // ignore previous node upon which we have used BFS\n                }\n            }\n            while (visitedGeneSet[curMin]) curMin++; // search current minimum, at most O(n)\n            ans[k] = curMin;\n            doNotVisit = k;\n            k = parents[k]; // visit next node in path (gene:1 -> root)\n        }\n        return ans;\n    }\n}\n```
['Java']