algorithms/algorithms/tree/path_sum.py at master · keon/algorithms · GitHub

Name: algorithms/algorithms/tree/path_sum.py at master · keon/algorithms · GitHub
Rating: 4.6 (7335 reviews)
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.
"""


defhas_path_sum(root, sum):
"""
 :type root: TreeNode
 :type sum: int
 :rtype: bool
 """
ifrootisNone:
returnFalse
ifroot.leftisNoneandroot.rightisNoneandroot.val==sum:
returnTrue
sum-=root.val
returnhas_path_sum(root.left, sum) orhas_path_sum(root.right, sum)


# DFS with stack
defhas_path_sum2(root, sum):
ifrootisNone:
returnFalse
stack= [(root, root.val)]
whilestack:
node, val=stack.pop()
ifnode.leftisNoneandnode.rightisNone:
ifval==sum:
returnTrue
ifnode.leftisnotNone:
stack.append((node.left, val+node.left.val))
ifnode.rightisnotNone:
stack.append((node.right, val+node.right.val))
returnFalse


# BFS with queue
defhas_path_sum3(root, sum):
ifrootisNone:
returnFalse
queue= [(root, sum-root.val)]
whilequeue:
node, val=queue.pop(0) # popleft
ifnode.leftisNoneandnode.rightisNone:
ifval==0:
returnTrue
ifnode.leftisnotNone:
queue.append((node.left, val-node.left.val))
ifnode.rightisnotNone:
queue.append((node.right, val-node.right.val))
returnFalse