FilesExpand file tree

 master

/

pathSum.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

21 lines (14 loc) · 473 Bytes

 master

/

pathSum.py

Copy path

Top

File metadata and controls

• Code
• Blame

21 lines (14 loc) · 473 Bytes

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

def pathSum(self, root, target):

self.result = 0

cache = {0:1}

def dfs(root, currPathSum):

if not root: return

currPathSum += root.val

oldPathSum = currPathSum - target

self.result += cache.get(oldPathSum, 0)

cache[currPathSum] = cache.get(currPathSum, 0) + 1

dfs(root.left, currPathSum)

dfs(root.right, currPathSum)

cache[currPathSum] -= 1

dfs(root, 0)

return self.result