Path Sum III – Leetcode Challenge – Python Solution
This is the python solution for the Leetcode problem – Path Sum III – Leetcode Challenge – Python Solution.
Source – qiyuangong’s repository.
# 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
