113. 路径总和 II

题目链接：https://leetcode-cn.com/problems/path-sum-ii/
难度：中等

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

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

题解

from copy import copy
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
        ret = []
        path = []
        def recursion(root, target_sum):
            if root is None:
                return
            path.append(root.val)
            target_sum -= root.val
            # 说明到了叶节点且符合条件
            if root.left is None and root.right is None and target_sum == 0:
                ret.append(copy(path))
            recursion(root.left, target_sum)
            recursion(root.right, target_sum)
            path.pop() # 经该节点的路径不可行，删除该节点
        recursion(root, targetSum)
        return ret