prep-coding/leetcode/PathSum.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
# 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 checkSum(self,
                curr: TreeNode,
                accumulator : int,
                targetSum : int):

        if (curr == None):
            return False

        accumulator += curr.val

        if (accumulator == targetSum and curr.left == None and curr.right == None):
            return True

        return self.checkSum(curr.left,
                             accumulator,
                             targetSum) or self.checkSum(curr.right,
                                                         accumulator,
                                                         targetSum)

    def hasPathSum(self, root: TreeNode, targetSum: int) -> bool:

        if (root == None):
            return False

        if (root.val == targetSum and root.left == None and root.right == None):
            return True

        return self.checkSum(root.left,
                             root.val,
                             targetSum) or self.checkSum(root.right,
                                                         root.val,
                                                         targetSum)