python - path sum III


  • 0
    S
    # Definition for a binary tree node.
    # class TreeNode(object):
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    
    class Solution(object):
        def npath(self, root, rsum, target, tbl, count):
            
            if root:        
                count += 1 if (rsum + root.val == target) else 0
                count += tbl.get(rsum + root.val - target, 0)
            
                tbl[rsum + root.val] = tbl.get(rsum + root.val, 0) + 1
            
                count = self.npath(root.left, rsum + root.val, target, tbl, count)
                count = self.npath(root.right, rsum + root.val, target, tbl, count)
            
                tbl[rsum + root.val] -= 1  
            
            return count
            
        def pathSum(self, root, sum):
            """
            :type root: TreeNode
            :type sum: int
            :rtype: int
            """
            return self.npath(root, 0, sum, {}, 0)
    

Log in to reply
 

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