Path Sum III

Question

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: 
[10,5,-3] 
[10,3,2,-2] 
[5,3,2,1]

Solution

▭

all//Path Sum III.py

# 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)

▯

all//Path Sum III.py

# 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)