刷题使我快乐，满脸开心.jpg

• 来源：力扣（LeetCode）
• 链接：https://leetcode.cn/problems/path-sum-ii/
• 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题目

给你二叉树的根节点 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
输出：[]

示例 3：

输入：root = [1,2], targetSum = 0
输出：[]

提示：

• 树中节点总数在范围 [0, 5000] 内
• -1000 <= Node.val <= 1000
• -1000 <= targetSum <= 1000

思路

虽然是个中等，但是只是一个搜索算法的简单变形，DFS和BFS均可

不过这里有一些需要注意的地方

• 元素值为整数，也就是可能为负的，虽然示例中没有出现，但是不要忽略这里，否则可能会出现多余的剪枝
• 缓存路径的方式需要注意，只用一个变量保存所有路径时别忘了恢复现场

上代码

代码

func pathSum(root *TreeNode, targetSum int) [][]int {
	res := make([][]int, 0)
    // 把路径传递下去空间复杂度会高，但是省的恢复现场
    // 否则的话，可只用一个变量，每层退出时去掉本层元素
	var findPath func(root *TreeNode, temp []int, left int)
	findPath = func(root *TreeNode, temp []int, left int) {
		if root == nil {
			return
		}
		temp = append(temp, root.Val)
		if left == root.Val && root.Left == nil && root.Right == nil {
			res = append(res, append([]int{}, temp...))
		}
		findPath(root.Left, temp, left-root.Val)
		findPath(root.Right, temp, left-root.Val)
	}
	findPath(root, make([]int, 0), targetSum)
	return res
}