prep-coding/leetcode/PathSumII.py at master · tushar-sharma/prep-coding · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution:

    def recCheckSum(self,
                    curr: TreeNode,
                    accumulator,
                    targetSum,
                    paths,
                    parent):

        if curr == None:
            return False

        accumulator += curr.val

        parent.append(curr.val)

        if accumulator == targetSum and curr.left == None and curr.right == None:
            paths.append(parent)


        self.recCheckSum(curr.left, accumulator, targetSum, paths, parent[:])

        self.recCheckSum(curr.right, accumulator, targetSum, paths, parent[:])

    def pathSum(self, root: TreeNode, targetSum: int) -> List[List[int]]:

        paths = []

        if root == None:
            return paths

        if root.val == targetSum and root.left == None and root.right == None:
            temp = []
            temp.append(root.val)

            paths.append(temp)

            return paths

        self.recCheckSum(root.left, root.val , targetSum, paths, [root.val])

        self.recCheckSum(root.right, root.val , targetSum, paths, [root.val])

        return paths