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
26
27
28
29
30
31
32
33
func pathSum(root *TreeNode, targetSum int) [][]int {
var res [][]int
var path []int
var dfs func(node *TreeNode, curSum int)
dfs = func(node *TreeNode, curSum int) {
if node == nil {
return
}
// 将当前节点值加入路径
path = append(path, node.Val)
curSum += node.Val
// 判断是否到达叶子节点且路径和等于目标和
if node.Left == nil && node.Right == nil && curSum == targetSum {
// 将当前路径加入结果集
temp := make([]int, len(path))
copy(temp, path)
res = append(res, temp)
}
// 递归遍历左子树和右子树
dfs(node.Left, curSum)
dfs(node.Right, curSum)
// 回溯，移除当前节点值
path = path[:len(path)-1]
}
dfs(root, 0)
return res
}
时间复杂度：O(N)，其中 N 是二叉树的节点数。每个节点遍历一次。
空间复杂度：O(N)，递归调用栈的深度和路径记录的空间。
1
write your code here
本博客所有文章除特别声明外，均采用
CC BY-NC-SA 4.0
许可协议，转载请注明出处！