2019-11-17

Python

class Solution(object):
    def nextLargerNodes(self, head):
        """
        :type head: ListNode
        :rtype: List[int]
        """
        stack = []
        ans = []
        cnt = 0
        while head:
            ans.append(0)
            while stack and stack[-1][0] < head.val:
                tv, ti = stack.pop()
                ans[ti] = head.val
            stack.append((head.val, cnt))
            cnt += 1
            head = head.next
        return ans

class Solution(object):
    def pathSum(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        dmap = {1 : 0}
        leaves = set([1])
        for num in nums:
            path, val = num / 10, num % 10
            lvl, seq = path / 10, path % 10
            parent = (lvl - 1) * 10 + (seq + 1) / 2
            dmap[path] = dmap[parent] + val
            leaves.add(path)
            if parent in leaves: leaves.remove(parent)
        return sum(dmap[v] for v in leaves)

class Solution(object):
    def findDuplicateSubtrees(self, root):
        """
        :type root: TreeNode
        :rtype: List[TreeNode]
        """
        treeMap = collections.defaultdict(list)
        def flattenTree(root):
            if not root:
                ans = '#'
            else:
                ans = '%s(%s,%s)' % (root.val, flattenTree(root.left), flattenTree(root.right))
                treeMap[ans].append(root)
            return ans
        flattenTree(root)
        return [v[0] for v in treeMap.values() if len(v) > 1]