Python Easy to Understand


  • 2
    class Solution(object):
        def pathSum(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            total, nodes_map = 0, {}
            def num_to_tuple(num, i):
                # The node 113 becomes a tuple of (0, 0, 3).
                depth, pos, value = int(str(num)[0]) - 1, int(str(num)[1]) - 1, int(str(num)[2])
                if depth not in nodes_map:
                    nodes_map[depth] = {}
                nodes_map[depth][pos] = i
                return (depth, pos, value)
            # Convert numbers to tuples.
            nodes = [num_to_tuple(num, i) for i, num in enumerate(nums)]
            path_sums = [0] * len(nodes)
    
            for index, node in enumerate(nodes):
                depth, pos, value = node
                path_sums[index] = value
                # Look up the dictionary for the node's parent.
                if depth - 1 in nodes_map and (pos // 2) in nodes_map[depth - 1]:
                    # If node has a parent, add the parent's value to the path sum.
                    path_sums[index] += path_sums[nodes_map[depth - 1][pos // 2]]
                # Look up the dictionary for the node's children.
                if not (depth + 1 in nodes_map and ((pos * 2) in nodes_map[depth + 1] or (pos * 2 + 1) in nodes_map[depth + 1])):
                    # If there are no children, it is a leaf. Add the path sum to the total.
                    total += path_sums[index]
            return total
    

    - Yangshun


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.