FilesExpand file tree

 master

/

path_sum.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

63 lines (56 loc) · 1.61 KB

 master

/

path_sum.py

Copy path

Top

File metadata and controls

• Code
• Blame

63 lines (56 loc) · 1.61 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

"""

Given a binary tree and a sum, determine if the tree has a root-to-leaf

path such that adding up all the values along the path equals the given sum.

For example:

Given the below binary tree and sum = 22,

5

/ \

4 8

/ / \

11 13 4

/ \ \

7 2 1

return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

"""

def has_path_sum(root, sum):

"""

:type root: TreeNode

:type sum: int

:rtype: bool

"""

if not root:

return False

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

return True

sum -= root.val

return has_path_sum(root.left, sum) or has_path_sum(root.right, sum)

# DFS with stack

def has_path_sum2(root, sum):

if not root:

return False

stack = [(root, root.val)]

while stack:

node, val = stack.pop()

if not node.left and not node.right:

if val == sum:

return True

if node.left:

stack.append((node.left, val+node.left.val))

if node.right:

stack.append((node.right, val+node.right.val))

return False

# BFS with queue

def has_path_sum3(root, sum):

if not root:

return False

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

while queue:

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

if not node.left and not node.right:

if val == 0:

return True

if node.left:

queue.append((node.left, val-node.left.val))

if node.right:

queue.append((node.right, val-node.right.val))

return False