200ms in python


  • 2
    W
        # Definition for a  binary tree node
    # class TreeNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    
    class Solution:
    

    Just tricks on list.200ms in python

        # @param root, a tree node
        # @param sum, an integer
        # @return a list of lists of integers
        def pathSum(self, root, sum):
            #   avoid null tree
            if root is None:
                return []
            
            def inter(root,sum):
                output = list()
                if root is None:
                    return []
                # leaf
                if root.left is None and root.right is None:
                    if root.val==sum:
                        return [[root.val]]
                    else:
                        return []
                if root.left is not None:
                    ret = inter(root.left, sum-root.val)
                    for i in range(len(ret)):
                        ret[i].insert(0,root.val)
                        # ret[i].append(root.val)
                        output.append(ret[i])
                if root.right is not None:
                    ret = inter(root.right, sum-root.val)
                    for i in range(len(ret)):
                        ret[i].insert(0,root.val)
                        # ret[i].append(root.val)
                        output.append(ret[i])
                
                return output
            
            return inter(root,sum)

  • 0
    C

    Same idea, different writing:

    def pathSum(self, root, sum):
        if root is None:
            return []
        if root.left is None and root.right is None and root.val == sum:
            return [[root.val]]
        left = self.pathSum(root.left, sum - root.val) if root.left else []
        right = self.pathSum(root.right, sum -root.val) if root.right else []
        return [[root.val] + elt for elt in left + right]

Log in to reply
 

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