forked from wuduhren/leetcode-python
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathpath-sum-ii.py
More file actions
20 lines (18 loc) · 700 Bytes
/
path-sum-ii.py
File metadata and controls
20 lines (18 loc) · 700 Bytes
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution(object):
def pathSum(self, root, S):
if not root: return False
opt = []
stack = []
stack.append((root, 0, []))
while stack:
node, s, path = stack.pop()
s += node.val
path = path + [node.val]
if not node.left and not node.right and s==S: opt.append(path)
if node.left: stack.append((node.left, s, path))
if node.right: stack.append((node.right, s, path))
return opt
"""
Time complexity is O(N), because we traverse all the nodes.
Space complexity is O(N^2), because in the worst case, all node could carry all the other nodes in the `path`.
"""