34. 二叉树中和为某一值的路径.md

解题思路

1. 回溯

当进入某个节点时，记录下到该点的路径，更新 target 值。 当到叶子节点，且 target 为路径和时，就将这一条路径加入到结果集

var ans [][]int
func pathSum(root *TreeNode, target int) [][]int {
    ans = make([][]int, 0)
    dfs(root, make([]int, 0), target)
    return ans
}

func dfs(root *TreeNode, res []int, target int) {
    if root == nil {
        return
    }
    // 当 root 当前为叶子节点时
    if root.Left == nil && root.Right == nil {
        // 如果 target 满足路径和，就将这条路径加入到结果集
        if target - root.Val == 0 {
            res = append(res, root.Val)
            ans = append(ans, append([]int{}, res...))
        }
        return
    }
    // 左右子树分别判断
    dfs(root.Left, append(res, root.Val), target-root.Val)
    dfs(root.Right, append(res, root.Val), target-root.Val)
}