题目
Given the root of a binary tree and an integer targetSum, return all root-to-leaf paths where each path’s sum equals targetSum.
A leaf is a node with no children.
解题思路
从根开始进行BFS或者DFS，遍历的时候维护路径和当前的和，到达叶节点判断是否等于target，如果是加到结果里
代码
class Solution:
def pathSum(self, root: TreeNode, targetSum: int) -> List[List[int]]:
if not root:
return []
q = [(root, root.val, [root.val])]
res = []
while q:
cur, s, path = q.pop()
if not cur.left and not cur.right and s == targetSum:
res.append(path)
if cur.left:
q.append((cur.left, s + cur.left.val, path + [cur.left.val]))
if cur.right:
q.append((cur.right, s + cur.right.val, path + [cur.right.val]))
return res
