Java | DFS + LinkedList | Merge LinkedList
\n\nclass Solution {\n    private class LLNode {\n        int low;\n        int high;\n        LLNode next;\n\n        public LLNode(int low, int high) {\n     
```\n\nclass Solution {\n    private class LLNode {\n        int low;\n        int high;\n        LLNode next;\n\n        public LLNode(int low, int high) {\n            this.low = low;\n            this.high = high;\n            this.next = null;\n        }\n    }\n\n    public int[] smallestMissingValueSubtree(int[] parents, int[] nums) {\n        int n = parents.length, parent = 0;\n        int[] ans = new int[n];\n        Set<Integer> children = null;\n        Map<Integer, Set<Integer>> childrenByNode = new HashMap<>();\n        for(int index = 0; index < n; index++) {\n            parent = parents[index];\n            children = childrenByNode.getOrDefault(parent, new HashSet<>());\n            children.add(index);\n            childrenByNode.put(parent, children);\n        }\n        getMergedList(childrenByNode, nums, ans, 0);\n        return ans;\n    }\n\n    private LLNode getMergedList(Map<Integer, Set<Integer>> childrenByNode, int[] nums, int[] ans, int node) {\n        LLNode head = new LLNode(nums[node], nums[node]);\n        if(!childrenByNode.containsKey(node)) {\n            ans[node] = ((nums[node] == 1) ? 2 : 1);\n            return head;\n        }\n        List<LLNode> lists = new ArrayList<>();\n        lists.add(head);\n        for(Integer child : childrenByNode.get(node)) {\n            lists.add(getMergedList(childrenByNode, nums, ans, child));\n        }\n        LLNode merged = mergedList(lists);\n        ans[node] = getFirstMissing(merged);\n        return merged;\n    }\n\n    private LLNode mergedList(List<LLNode> lists) {\n        LLNode head = null, tail = null, current = null, next = null;\n        PriorityQueue<LLNode> queue = new PriorityQueue<>(new Comparator<>() {\n            public int compare(LLNode left, LLNode right) {\n                return (left.low - right.low);\n            }\n        });\n        for(LLNode node : lists) {\n            queue.add(node);\n        }\n        while(!queue.isEmpty()) {\n            current = queue.poll();\n            next = current.next;\n            current.next = null;\n            if(head == null) {\n                head = current;\n                tail = current;\n            } else {\n                if((tail.high + 1) == current.low) {\n                    tail.high = current.high;\n                } else {\n                    tail.next = current;\n                    tail = current;\n                }\n            }\n            if(next != null) {\n                queue.add(next);\n            }\n        }\n        return head;\n    }\n\n    private int getFirstMissing(LLNode list) {\n        if(list.low > 1) {\n            return 1;\n        }\n        return (list.high + 1);\n    }\n}\n\n```
[]