113. Path Sum II
Difficulty: Medium
Given a binary tree and a sum, find all root-to-leaf paths where each path’s sum equals the given sum.
Note: A leaf is a node with no children.
Example:
Given the below binary tree and sum = 22,
1
2
3
4
5
6
7
|
5
/
4 8
/ /
11 13 4
/ /
7 2 5 1
|
Return:
1
2
3
4
|
[
[5,4,11,2],
[5,8,4,5]
]
|
解法
-
层序遍历
- 一个treemap存放每个结点到前驱结点的映射，方便回溯路径；
- 一个队列用于层序遍历，存放结点和结点路径和的二元组；
-
DFS
代码
- 层序
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
|
class :
def get_path(self, tree_map, node):
path = []
while tree_map[node] is not None:
path.insert(0,node.val)
node = tree_map[node]
path.insert(0,node.val)
return path
def pathSum(self, root: TreeNode, sum: int) -> List[List[int]]:
if root is None:
return []
queue = [(root, root.val)]
tree_map = {root:None}
result = []
while len(queue)>0:
node, path_sum = queue.pop(0)
if (node.left is None and node.right is None) and (path_sum == sum):
result.append(self.get_path(tree_map, node))
if node.left:
tree_map[node.left] = node
queue.append((node.left, path_sum+node.left.val))
if node.right:
tree_map[node.right] = node
queue.append((node.right, path_sum+node.right.val))
return result
|
- DFS
1
2
3
4
5
6
7
8
9
10
11
12
13
|
class :
def pathSum(self, root: TreeNode, sum: int) -> List[List[int]]:
def helper(path, pathSum, root):
if root:
newPathSum = pathSum + root.val
if newPathSum == sum and not root.left and not root.right:
res.append(path + [root.val])
return
helper(path + [root.val], newPathSum, root.left)
helper(path + [root.val], newPathSum, root.right)
res = []
helper([], 0, root)
return res
|
- 其他DFS实现
1
2
3
4
5
6
7
8
|
def dfs(root, out, sum):
if not root: return
out.append(root.val)
if sum == root.val and not root.left and not root.right:
self.res.append(out[:])
dfs(root.left, out, sum - root.val)
dfs(root.right, out, sum - root.val)
out.pop()
|
1
2
3
4
5
6
7
8
9
10
11
12
|
class :
def pathSum(self, root: TreeNode, sum: int) -> List[List[int]]:
if root is None:
return []
if root.left is None and root.right is None and root.val == sum:
return [[root.val]]
sum -= root.val
temp = self.pathSum(root.left, sum) + self. pathSum(root.right, sum)
return [[root.val]+ i for i in temp]
|
近期评论