```
class Solution(object):
def pathSum(self, root, sum):
self.ans = 0
def dfs(r, s, f):
if not r:
return
if s == sum:
self.ans += 1
if r.left:
dfs(r.left, s + r.left.val, f + 1)
if r.right:
dfs(r.right, s + r.right.val, f + 1)
if f == 1:
dfs(r, r.val, 0)
if not root:
return 0
dfs(root, root.val, 0)
return self.ans
```