package main
import . "nc_tools"

//递归,别想迭代了,空间不如,还贼复杂,递归才是通法
var res [][]int
func pathSum( root *TreeNode ,  sum int ) [][]int {
    res = [][]int{}
    path := []int{}
    dfs(root, sum, path)

    return res
}

func dfs(root *TreeNode, sum int, path []int) {
    if root == nil {
        return
    }

    path = append(path, root.Val)

    if root.Left == nil && root.Right == nil && root.Val == sum {
        tmp := make([]int, len(path))
        copy(tmp, path)
        res = append(res, tmp)
    }

    dfs(root.Left, sum - root.Val, path)
    dfs(root.Right, sum - root.Val, path)
}