路径问题BFS和DFS模板
给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
叶子节点 是指没有子节点的节点。
实例1
输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22 输出：[[5,4,11,2],[5,8,4,5]]
实例2
输入：root = [1,2,3], targetSum = 5 输出：[]
其实轮模板，我觉得BFS的模板是比DFS的模板更容易的，因为相对来说，各种题目中，BFS的解法更容易让人迅速理解。下面就是用BFS模板写出来的解答
class Solution:
def pathSum(self, root: TreeNode, sum: int) -> List[List[int]]:
if not root:
return []
res = []
que=deque([(root, [root.val], root.val)]) # 初始化当前节点 当前路径 当前路径和
while que:
node,path,curr_sum=que.popleft() # bfs的经典套路模板
if not node.left and not node.right and curr_sum==sum:
res.append(path)
if node.left:
que.append((node.left,path+[node.left.val],curr_sum+node.left.val))
if node.right:
que.append((node.right,path+[node.right.val],curr_sum+node.right.val))
return res
分析
路径问题用dfs和bfs是比较合适的，路径总和第一题leetcode112 只是需要返回是否存在，也就是True or False。而第二题需要返回路径。
先看看第一题的dfs解法。
class Solution:
def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
if root is None:
return False
if not root.left and not root.right:
return targetSum==root.val
return self.hasPathSum(root.left,targetSum-root.val)
or self.hasPathSum(root.right,targetSum-root.val)
而路径总和2和1的区别在于怎么处理path和paths。
最直接的解法就是直接把path和paths也加入到递归中,由于path和paths也是不断更新的，是选择写成全局变量，一个Solution类中的两个平行的函数，还是将新构造的函数写成函数中的函数，我选择了后者，因为我觉得这样能够避免path和paths递归中深或者浅拷贝遇到的麻烦。
解法1
# 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: Optional[TreeNode], targetSum: int) -> List[List[int]]:
def dfs(root, targetSum, path, paths):
if not root :
return []
if not root.left and not root.right and targetSum==root.val:
path.append(root.val)
paths.append(path)
dfs(root.left, targetSum-root.val, path+[root.val], paths)
dfs(root.right, targetSum-root.val, path+[root.val], paths)
path=[]
paths=[]
dfs(root, targetSum, path, paths)
return paths
优化版本，也是官方版本
class Solution:
def pathSum(self, root: TreeNode, sum: int) -> List[List[int]]:
result = []
path = []
def explore(node, release):
if not node:
return
path.append(node.val)
release -= node.val
if any((node.left, node.right)):
explore(node.left, release)
explore(node.right, release)
else:
if release == 0:
result.append(path[:])
path.pop()
explore(root, sum)
return result
