# LeetCode 437Path Sum III

## LeetCode 437 Path Sum III Problem

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

# https://leetcode.com/problems/path-sum-iii/discuss/91892/Python-solution-with-detailed-explanation
class Solution(object):
# def find_paths(self, root, target):
#     if root:
#         return int(root.val == target)
#         + self.find_paths(root.left, target - root.val)
#         + self.find_paths(root.right, target - root.val)
#     return 0

# def pathSum(self, root, sum):
#     """
#     :type root: TreeNode
#     :type sum: int
#     :rtype: int
#     """
#     if root:
#         return self.find_paths(root, sum)
#         + self.pathSum(root.left, sum)
#         + self.pathSum(root.right, sum)
#     return 0

def pathSumHelper(self, root, target, so_far, cache):
if root:
# complement == 1, root->curr path
complement = so_far + root.val - target
if complement in cache:
# S->E path, sum(root->S)-sum(root->E) = target
self.result += cache[complement]
cache[so_far + root.val] = cache.get(so_far + root.val, 0) + 1
self.pathSumHelper(root.left, target, so_far + root.val, cache)
self.pathSumHelper(root.right, target, so_far + root.val, cache)
cache[so_far + root.val] -= 1
return

def pathSum(self, root, sum):
"""
:type root: TreeNode
:type sum: int
:rtype: int
"""
self.result = 0
self.pathSumHelper(root, sum, 0, {0: 1})
return self.result
``````

## List of all Path Sum III problems

Leetcode 437 Path Sum III problem solution in python3 with explanation. This is the best place to expand your knowledge and get prepared for your next interview.

self.val = x

self.left = None

Feedback is the most important part of any website.