每日一题：LeetCode-113. 路径总和 II

作者：半亩房顶

2023-12-15
北京
本文字数：787 字
阅读完需：约 3 分钟

刷题使我快乐，满脸开心.jpg

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/path-sum-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]]

复制代码

示例 2：

输入：root = [1,2,3], targetSum = 5输出：[]

复制代码

示例 3：

输入：root = [1,2], targetSum = 0输出：[]

复制代码

提示：

树中节点总数在范围 [0, 5000] 内
-1000 <= Node.val <= 1000
-1000 <= targetSum <= 1000

思路

虽然是个中等，但是只是一个搜索算法的简单变形，DFS和BFS均可

不过这里有一些需要注意的地方

元素值为整数，也就是可能为负的，虽然示例中没有出现，但是不要忽略这里，否则可能会出现多余的剪枝
缓存路径的方式需要注意，只用一个变量保存所有路径时别忘了恢复现场

上代码

代码

func pathSum(root *TreeNode, targetSum int) [][]int {    res := make([][]int, 0)    // 把路径传递下去空间复杂度会高，但是省的恢复现场    // 否则的话，可只用一个变量，每层退出时去掉本层元素    var findPath func(root *TreeNode, temp []int, left int)    findPath = func(root *TreeNode, temp []int, left int) {        if root == nil {            return        }        temp = append(temp, root.Val)        if left == root.Val && root.Left == nil && root.Right == nil {            res = append(res, append([]int{}, temp...))        }        findPath(root.Left, temp, left-root.Val)        findPath(root.Right, temp, left-root.Val)    }    findPath(root, make([]int, 0), targetSum)    return res}