forked from shuboc/LeetCode-2
-
Notifications
You must be signed in to change notification settings - Fork 0
/
path-sum-iii.py
89 lines (78 loc) · 2.22 KB
/
path-sum-iii.py
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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
# Time: O(n)
# Space: O(h)
# You are given a binary tree in which each node contains an integer value.
#
# Find the number of paths that sum to a given value.
#
# The path does not need to start or end at the root or a leaf,
# but it must go downwards (traveling only from parent nodes to child nodes).
#
# The tree has no more than 1,000 nodes and the values are in the range -1,000,000 to 1,000,000.
#
# Example:
#
# root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8
#
# 10
# / \
# 5 -3
# / \ \
# 3 2 11
# / \ \
# 3 -2 1
#
# Return 3. The paths that sum to 8 are:
#
# 1. 5 -> 3
# 2. 5 -> 2 -> 1
# 3. -3 -> 11
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
import collections
class Solution(object):
def pathSum(self, root, sum):
"""
:type root: TreeNode
:type sum: int
:rtype: int
"""
def pathSumHelper(root, curr, sum, lookup):
if root is None:
return 0
curr += root.val
result = lookup[curr-sum] if curr-sum in lookup else 0
lookup[curr] += 1
result += pathSumHelper(root.left, curr, sum, lookup) + \
pathSumHelper(root.right, curr, sum, lookup)
lookup[curr] -= 1
if lookup[curr] == 0:
del lookup[curr]
return result
lookup = collections.defaultdict(int)
lookup[0] = 1
return pathSumHelper(root, 0, sum, lookup)
# Time: O(n^2)
# Space: O(h)
class Solution2(object):
def pathSum(self, root, sum):
"""
:type root: TreeNode
:type sum: int
:rtype: int
"""
def pathSumHelper(root, prev, sum):
if root is None:
return 0
curr = prev + root.val;
return int(curr == sum) + \
pathSumHelper(root.left, curr, sum) + \
pathSumHelper(root.right, curr, sum)
if root is None:
return 0
return pathSumHelper(root, 0, sum) + \
self.pathSum(root.left, sum) + \
self.pathSum(root.right, sum)