cs-book

路径总和II

  type TreeNode struct {
      Val int
      Left *TreeNode
      Right *TreeNode
  }

func pathSum(root *TreeNode, targetSum int) [][]int {
	  var dfs func(node *TreeNode, sum int, path []int, result *[][]int)
      
	  dfs = func(node *TreeNode, sum int, path []int, result *[][]int) {
	  	if node == nil {
	  		return
	  	}
      
	  	// 添加当前节点的值到路径中
	  	path = append(path, node.Val)
	  	sum -= node.Val
      
	  	// 检查是否到达叶子节点且路径和等于目标值
	  	if sum == 0 && node.Left == nil && node.Right == nil {
	  		// 复制当前路径以防止修改影响结果集
	  		tmp := make([]int, len(path))
	  		copy(tmp, path)
	  		*result = append(*result, tmp)
	  	}
      
	  	// 继续递归遍历左子树和右子树
	  	dfs(node.Left, sum, path, result)
	  	dfs(node.Right, sum, path, result)
      
	  	// 回溯：移除路径中的最后一个节点
	  	path = path[:len(path)-1]
	  }
      
	  var result [][]int
	  dfs(root, targetSum, []int{}, &result)
	  return result
}