FilesExpand file tree

 master

/

path_sum2.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

70 lines (62 loc) · 1.66 KB

 master

/

path_sum2.py

Copy path

Top

File metadata and controls

• Code
• Blame

70 lines (62 loc) · 1.66 KB

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

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

"""

Given a binary tree and a sum, find all root-to-leaf

paths where each path's sum equals the given sum.

For example:

Given the below binary tree and sum = 22,

5

/ \

4 8

/ / \

11 13 4

/ \ / \

7 2 5 1

return

[

[5,4,11,2],

[5,8,4,5]

]

"""

def path_sum(root, sum):

if not root:

return []

res = []

DFS(root, sum, [], res)

return res

def DFS(root, sum, ls, res):

if not root.left and not root.right and root.val == sum:

ls.append(root.val)

res.append(ls)

if root.left:

DFS(root.left, sum-root.val, ls+[root.val], res)

if root.right:

DFS(root.right, sum-root.val, ls+[root.val], res)

# DFS with stack

def path_sum2(root, s):

if not root:

return []

res = []

stack = [(root, [root.val])]

while stack:

node, ls = stack.pop()

if not node.left and not node.right and sum(ls) == s:

res.append(ls)

if node.left:

stack.append((node.left, ls+[node.left.val]))

if node.right:

stack.append((node.right, ls+[node.right.val]))

return res

# BFS with queue

def path_sum3(root, sum):

if not root:

return []

res = []

queue = [(root, root.val, [root.val])]

while queue:

node, val, ls = queue.pop(0) # popleft

if not node.left and not node.right and val == sum:

res.append(ls)

if node.left:

queue.append((node.left, val+node.left.val, ls+[node.left.val]))

if node.right:

queue.append((node.right, val+node.right.val, ls+[node.right.val]))

return res