Deepest Leaves Sum

Intuition

Use DFS with 2 additional return value leaves_sum and depth. For each node, if it's left depth is the same as right depth, return the sum of 2 value. Else, return the leaves_sum and depth of the deepest children.

Solution


# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def deepestLeavesSum(self, root: TreeNode) -> int:
        return self._dfs(root, 0)[0]

    def _dfs(self, node, depth):
        if node.left and node.right:
            l = self._dfs(node.left, depth + 1)
            r = self._dfs(node.right, depth + 1)
            if l[1] == r[1]:
                return l[0] + r[0], l[1]
            elif l[1] > r[1]:
                return l
            else:
                return r
        elif node.left is not None:
            return self._dfs(node.left, depth + 1)
        elif node.right is not None:
            return self._dfs(node.right, depth + 1)
        else:
            # This is a leaf node
            return node.val, depth