dfs-with-checking-condition-path-sum-ii.py

# 113. Path Sum II
# Medium

# Given the root of a binary tree and an integer targetSum, return all root-to-leaf paths where each path's sum equals targetSum.

# A leaf is a node with no children.

#https://assets.leetcode.com/uploads/2021/01/18/pathsumii1.jpg
#Input: root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
#Output: [[5,4,11,2],[5,8,4,5]]

# Input: root = [1,2,3], targetSum = 5
# Output: []

# Input: root = [1,2], targetSum = 0
# Output: []

# 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: TreeNode, targetSum: int) -> List[List[int]]:
        
        retList = []
        
        def dfs(root,targetSum,tempdfs=[]):
            
            if root is None:
                return 
            
            if not root.left and not root.right and root.val == targetSum:
                tempdfs.append(root.val)
                print(tempdfs)
                retList.append(tempdfs.copy())
                tempdfs.pop()
                return
            

            targetSum -= root.val
            tempdfs.append(root.val)
            print(tempdfs)
            dfs(root.left,targetSum,tempdfs)
            print(tempdfs)
            dfs(root.right,targetSum,tempdfs)
            print(tempdfs)
            tempdfs.pop()

        
        
        dfs(root,targetSum)
        return retList