剑指 Offer 34. 二叉树中和为某一值的路径

题目描述

给你二叉树的根节点 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

链接：https://leetcode-cn.com/problems/er-cha-shu-zhong-he-wei-mou-yi-zhi-de-lu-jing-lcof
注意：本题与主站 113 题相同：https://leetcode-cn.com/problems/path-sum-ii/

解题思路

这里使用dfs来解决问题，不断判断当前走到的是不是叶子结点。（为什么不判断是不是走到了None？因为叶子结点的左右子结点都是None，会生成两个相同的pathSum）
如果dfs到了叶子结点，判断当前走过的路径和是不是满足targetSum，满足的话就给总结果增加当前走过的路径。

解题代码

class Solution:
    def dfs(self, node: TreeNode, path:list[int], now_sum: int, target: int):
        if not node:
            return
        new_sum = now_sum + node.val
        new_path = path.copy()
        new_path.append(node.val)
        if not node.left and not node.right and new_sum == target:
            self.path_all.append(new_path)
            return
        self.dfs(node.left, new_path, new_sum, target)
        self.dfs(node.right, new_path, new_sum, target)

    def pathSum(self, root: TreeNode, target: int) -> list[list[int]]:
        self.path_all = list()
        self.dfs(root, [], 0, target)
        return self.path_all

执行结果

执行结果：通过
执行用时：40 ms, 在所有 Python3 提交中击败了68.42%的用户
内存消耗：20.4 MB, 在所有 Python3 提交中击败了5.01%的用户

注意点

• 前序遍历即可
• 善用path.copy复制一个list，保存当前的状态
• 只有遍历到叶子节点才算走完一个路径，并加入path_all