路径总和系列
📌 定义
给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。
示例:
5
/ \
4 8
/ / \
11 13 4
/ \ / \
7 2 5 1
目标和 = 22
输出: [[5,4,11,2], [5,8,4,5]]
核心思路
使用回溯 + DFS遍历二叉树：
- 选择：访问当前节点
- 探索：递归访问左右子树
- 撤销：回溯到父节点
Go 代码
Go 实现
func pathSum(root *TreeNode, targetSum int) [][]int {
result := [][]int{}
path := []int{}
var backtrack func(node *TreeNode, remaining int)
backtrack = func(node *TreeNode, remaining int) {
if node == nil {
return
}
path = append(path, node.Val)
remaining -= node.Val
if node.Left == nil && node.Right == nil && remaining == 0 {
temp := make([]int, len(path))
copy(temp, path)
result = append(result, temp)
}
backtrack(node.Left, remaining)
backtrack(node.Right, remaining)
path = path[:len(path)-1]
}
backtrack(root, targetSum)
return result
}