https://leetcode.com/problems/path-sum-iii/#/description
# naive solution
# O(N^2)
class Solution(object):
def pathSum(self, root, sum):
"""
:type root: TreeNode
:type sum: int
:rtype: int
"""
self.count = 0
self.dfs(root, sum)
self.arr = []
return self.count
def dfs(self, root, sum):
if root:
self.helper(root, sum)
self.dfs(root.left, sum)
self.dfs(root.right, sum)
def helper(self, root, target):
if root:
if target == root.val:
self.count += 1
self.helper(root.left, target - root.val)
self.helper(root.right, target - root.val)
# similar to prefix sum array
# O(N)
class Solution(object):
def pathSum(self, root, sum):
"""
:type root: TreeNode
:type sum: int
:rtype: int
"""
self.count = 0
self.pre_sum = {0: 1}
self.helper(root, sum, 0)
return self.count
def helper(self, root, target, curr_sum):
if not root:
return
curr_sum += root.val
if curr_sum - target in self.pre_sum:
self.count += self.pre_sum[curr_sum - target]
self.pre_sum[curr_sum] = self.pre_sum.get(curr_sum, 0) + 1
self.helper(root.left, target, curr_sum)
self.helper(root.right, target, curr_sum)
self.pre_sum[curr_sum] -= 1
class Solution(object):
def pathSum(self, root, sum):
"""
:type root: TreeNode
:type sum: int
:rtype: int
"""
self.pre_sum = {0: 1}
res = self.helper(root, sum, 0)
return res
def helper(self, root, target, curr_sum):
if not root:
return 0
curr_sum += root.val
res = self.pre_sum.get(curr_sum - target, 0)
self.pre_sum[curr_sum] = self.pre_sum.get(curr_sum, 0) + 1
res += self.helper(root.left, target, curr_sum)
res += self.helper(root.right, target, curr_sum)
self.pre_sum[curr_sum] = self.pre_sum[curr_sum] - 1
return res
e437: path sum 3
e112: path sum 1
