-
Notifications
You must be signed in to change notification settings - Fork 35
Expand file tree
/
Copy path113_path_sum_ii.py
More file actions
39 lines (30 loc) · 835 Bytes
/
113_path_sum_ii.py
File metadata and controls
39 lines (30 loc) · 835 Bytes
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
"""
Definition for a binary tree node.
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
"""
class Solution:
def pathSum(self, root, target):
"""
:type root: TreeNode
:type target: int
:rtype: List[List[int]]
"""
ans = []
if not root:
return ans
self.dfs(root, target, ans, [])
return ans
def dfs(self, node, remaining, ans, path):
if not node:
return
path.append(node.val)
if not node.left and not node.right and remaining == node.val:
ans.append(path[:])
else:
self.dfs(node.left, remaining - node.val, ans, path)
self.dfs(node.right, remaining - node.val, ans, path)
path.pop()