题解 | #二叉树根节点到叶子节点和为指定值的路径# DFS+回溯

DFS+回溯

/**
  * 
  * @param root TreeNode类 
  * @param sum int整型 
  * @return int整型二维数组
*/
func pathSum( root *TreeNode ,  sum int ) [][]int {
    // write code here
    if root == nil {
        return nil
    }

    ret := make([][]int, 0)
    path := []int{root.Val}

    DFS(root, sum, root.Val, &path, &ret)

    return ret
}

// DFS
// target 目标值
// pathSum 目前的路径和   path 路径上各个节点值    ret 最终的结果
func DFS(root *TreeNode, target, pathSum int, path *[]int, ret *[][]int) {
//     已经到达叶子节点
    if root.Left == nil && root.Right == nil && pathSum == target {
        tmp := make([]int, len(*path))
        copy(tmp, *path)
        *ret = append(*ret, tmp)
        return
    }

//  左子节点
    if root.Left != nil {
        pathSum += root.Left.Val
        *path = append(*path, root.Left.Val)

        DFS(root.Left, target, pathSum, path, ret)

        pathSum -= root.Left.Val
        *path = (*path)[:len(*path)-1]
    }

//  右子节点
    if root.Right != nil {
        pathSum += root.Right.Val
        *path = append(*path, root.Right.Val)

        DFS(root.Right, target, pathSum, path, ret)

        pathSum -= root.Right.Val
        *path = (*path)[:len(*path)-1]
    }
}