Deepest Leaves Sum LeetCode solution in Python

1
# Definition for a binary tree node.
2
# class TreeNode(object):
3
#     def __init__(self, val=0, left=None, right=None):
4
#         self.val = val
5
#         self.left = left
6
#         self.right = right
7
class Solution(object):
8
    """
9
    THOUGHT PROCESS:
10
        1) find the height of the tree, this way we would know how deep we need to go.
11
        2) we need a counter to check how deep we are and this is not available in deepestLeavesSum so we create a new function deepestLeave.
12
        3) now we go in depth, if we are at bottom, we return the value, we recursively visit both left and right nodes.
13

14
    """
15

16
    def height(self, root):
17
        if root is None:
18
            return 0
19
        else:
20
            x, y = 1, 1
21
            if root.left:
22
                x = self.height(root.left) + 1
23
            if root.right:
24
                y = self.height(root.right) + 1
25

26
            return max(x, y)
27

28
    def deepestLeave(self, root, depth):
29

30
        if root is None:
31
            return 0
32

33
        if root.left is None and root.right is None:
34
            if depth == 1:
35
                return root.val
36

37
        return self.deepestLeave(root.left, depth - 1) + self.deepestLeave(
38
            root.right, depth - 1
39
        )
40

41
    def deepestLeavesSum(self, root):
42
        """
43
        :type root: TreeNode
44
        :rtype: int
45
        """
46
        return self.deepestLeave(root, self.height(root))