LeetCode 113. 路径总和 II
题目描述
思路分析
思路描述
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
func pathSum(root *TreeNode, targetSum int) [][]int {
res := make([][]int, 0)
if root == nil {
return res
}
dfs(root, targetSum, []int{root.Val}, &res)
return res
}
func dfs(node *TreeNode, pathSum int, path []int, res *[][]int) {
if node.Left == nil && node.Right == nil && pathSum == node.Val {
// 创建一个新的路径副本，以避免修改原始路径
tempPath := make([]int, len(path))
copy(tempPath, path)
*res = append(*res, tempPath)
}
if node.Left != nil {
newPath := append(path, node.Left.Val) // 创建新的路径副本
dfs(node.Left, pathSum-node.Val, newPath, res)
}
if node.Right != nil {
newPath := append(path, node.Right.Val) // 创建新的路径副本
dfs(node.Right, pathSum-node.Val, newPath, res)
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
type QueueNode struct {
Node *TreeNode
Sum int
Path []int
}
func pathSum(root *TreeNode, targetSum int) [][]int {
res := make([][]int, 0)
if root == nil {
return res
}
queue := []*QueueNode{&QueueNode{
Node: root,
Sum: root.Val,
Path: []int{root.Val},
}}
for len(queue) > 0 {
node, sum, path := queue[0].Node, queue[0].Sum, queue[0].Path
queue = queue[1:]
if node.Left == nil && node.Right == nil && sum == targetSum {
tempPath := make([]int, len(path))
copy(tempPath, path)
res = append(res, tempPath)
}
if node.Left != nil {
newPath := make([]int, len(path))
copy(newPath, path)
newPath = append(newPath, node.Left.Val)
queue = append(queue, &QueueNode{
Node: node.Left,
Sum: sum + node.Left.Val,
Path: newPath,
})
}
if node.Right != nil {
newPath := make([]int, len(path))
copy(newPath, path)
newPath = append(newPath, node.Right.Val)
queue = append(queue, &QueueNode{
Node: node.Right,
Sum: sum + node.Right.Val,
Path: newPath,
})
}
}
return res
}
1
write your code here
相似题目
| 题目 | 难度 | 题解 |
|---|---|---|
| 路径总和 | Easy | |
| 二叉树的所有路径 | Easy | |
| 路径总和 III | Medium | |
| 路径总和 IV | Medium |
本博客所有文章除特别声明外，均采用
CC BY-NC-SA 4.0
许可协议，转载请注明出处！