[Leetcode]27.路径总和 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
输出：[]

思想:深度优先 递归搜索,增加一个保存路径的数组,判断叶子结点是否符合目标要求。

func pathSum(root *TreeNode, targetSum int) [][]int {
	var visited []int
	var res [][]int
	if root == nil {
		return res
	}
	var dfs func(root *TreeNode, sum int, visited []int)
	dfs = func(root *TreeNode, sum int, visited []int) {
		visited = append(visited, root.Val)
		sum += root.Val
		if root.Left == nil && root.Right == nil {
			if sum == targetSum {
				res1 := make([]int, len(visited))
				for i := 0; i < len(visited); i++ {
					res1[i] = visited[i]
				}
				res = append(res, res1)
			}
		}
		if root.Left != nil {
			dfs(root.Left, sum, visited)
		}
		if root.Right != nil {
			dfs(root.Right, sum, visited)
		}
	}
	dfs(root, 0, visited)
	return res
}

题目来源：https://leetcode-cn.com/problems/path-sum-ii