Skip to main content

Path Sum III


Given a binary tree, find the total number of paths from the root node to leaf nodes where the sum of all the node values of the path equals a given target value.

Example 1
Input: root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8
Output: 3
Explanation: The paths that sum to 8 are:


all//Path Sum

# Definition for a binary tree node.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right

class Solution:
def pathSum(self, root, sum):
if not root:
return 0

return self.helper(root, sum) + self.pathSum(root.left, sum) + self.pathSum(root.right, sum)

def helper(self, node, sum):
if not node:
return 0

return int(node.val == sum) + self.helper(node.left, sum - node.val) + self.helper(node.right, sum - node.val)