dfs and merge intervals
For each node, merge the intervals of its children and itself. \n\nNot sure what others think, I understand this is not an optimal method, but I think the logic
For each node, merge the intervals of its children and itself. \n\nNot sure what others think, I understand this is not an optimal method, but I think the logic is straightforward. I had a concern about the time complexity, but it got ac.\n\n```\n    def smallestMissingValueSubtree(self, parents, nums):\n        """\n        :type parents: List[int]\n        :type nums: List[int]\n        :rtype: List[int]\n        """\n        res = [float("inf") for _ in range(len(parents))]\n        children = collections.defaultdict(set)\n        for index,i in enumerate(parents):\n            children[i].add(index)\n\n        def dfs(index):#the intervals of index node\n            if index not in children or len(children[index]) == 0:\n                if nums[index] == 1:\n                    res[index] = 2\n                else:\n                    res[index] = 1\n                return [[nums[index],nums[index]]]\n            leftarr = [[nums[index],nums[index]]]\n            cur = []\n            for child in children[index]:\n                rightarr = dfs(child)\n                left,right = 0,0\n                while left<len(leftarr) and right<len(rightarr):#merge the intervals, distinct values make the merging much easier\n                    if leftarr[left][0]<rightarr[right][0]:\n                        if rightarr[right][0] == leftarr[left][1]+1:\n                            rightarr[right][0] = leftarr[left][0]\n                        else:\n                            cur.append(leftarr[left])\n                        left += 1\n                    else:\n                        if rightarr[right][1]+1 == leftarr[left][0]:\n                            leftarr[left][0] = rightarr[right][0]\n                        else:\n                            cur.append(rightarr[right])\n                        right += 1\n                cur += leftarr[left:]\n                cur += rightarr[right:]\n                leftarr = cur\n                cur = []\n            if leftarr[0][0]!=1:\n                res[index] = 1\n            else:\n                res[index] = leftarr[0][1]+1\n            return leftarr\n        dfs(0)\n        return res\n
[]