给你二叉树的根节点 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
解题：
// 没解出来。。。官方解答：
1.深度优先搜索
func pathSum(root *TreeNode, targetSum int) (ans [][]int) {
var path []int
var dfs func(node *TreeNode, left int)
dfs = func(node *TreeNode, left int) {
if node == nil {
return
}
left -= node.Val
path = append(path, node.Val)
defer func() { path = path[:len(path)-1] }()
if node.Left == nil && node.Right == nil && left == 0 {
ans = append(ans, append([]int(nil), path...))
return
}
dfs(node.Left, left)
dfs(node.Right, left)
}
dfs(root, targetSum)
return
}2.广度优先搜索
type pair struct {
node *TreeNode
left int
}
func pathSum(root *TreeNode, targetSum int) (ans [][]int) {
if root == nil {
return
}
parent := map[*TreeNode]*TreeNode{}
getPath := func(node *TreeNode) (path []int) {
for ; node != nil; node = parent[node] {
path = append(path, node.Val)
}
for i, j := 0, len(path)-1; i < j; i++ {
path[i], path[j] = path[j], path[i]
j--
}
return
}
queue := []pair{{root, targetSum}}
for len(queue) > 0 {
p := queue[0]
queue = queue[1:]
node := p.node
left := p.left - node.Val
if node.Left == nil && node.Right == nil {
if left == 0 {
ans = append(ans, getPath(node))
}
} else {
if node.Left != nil {
parent[node.Left] = node
queue = append(queue, pair{node.Left, left})
}
if node.Right != nil {
parent[node.Right] = node
queue = append(queue, pair{node.Right, left})
}
}
}
return
}