一、简介

题目：路径总和II

给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。

叶子节点 是指没有子节点的节点。

案例1

输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出：[[5,4,11,2],[5,8,4,5]]

二、实现

思路：递归遍历，1.如果没有子节点，判断当前值是否等于查找的值；2.如果存在子节点，则遍历子节点

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func pathSum(root *TreeNode, targetSum int) [][]int {
    if root == nil {
        return nil
    }

    var res = make([][]int, 0)
    doPathSum(root, targetSum, []int{}, &res)

    return res
}

func doPathSum(root *TreeNode, targetSum int, curList []int , res *[][]int) {
    targetSum =  targetSum - root.Val
    curList = append(curList, root.Val)
    if root.Left == nil && root.Right == nil {
        if targetSum == 0 {
            b := make([]int, len(curList))
            copy(b, curList)
            
            *res = append(*res, b)
        }
        return
    } 

    if root.Left != nil {
        doPathSum(root.Left, targetSum, curList, res)
    }

    if root.Right != nil {
        doPathSum(root.Right, targetSum, curList, res)
    }
}