Подсчёт суммы значений листьев на самой глубокой уровне дерева

Условие

Дано бинарное дерево с корневым узлом treeRoot. Требуется вычислить сумму значений всех листовых узлов, расположенных на максимальной глубине дерева. Листовым считается узел, у которого отсутствуют дочерние элементы. Глубина узла определяется как количество рёбер от корня до данного узла.

Пример 1: Ввод: root = [1,2,3,4,5,null,6,7,null,null,null,null,8] Вывод: 15 Пояснение:

• Дерево: [1,2,3,4,5,null,6,7,null,null,null,null,8].
• Наибольшая глубина = 3 (узлы 7 и 8).
• Листовые узлы на глубине 3: 7 и 8.
• Сумма: 7 + 8 = 15.

Пример 2: Ввод: root = [6,7,8,2,7,1,3,9,null,1,4,null,null,null,5] Вывод: 19 Пояснение:

• Дерево: [6,7,8,2,7,1,3,9,null,1,4,null,null,null,5].
• Наибольшая глубина = 4 (узлы 9, 1, 4, 5).
• Листовые узлы на глубине 4: 9, 1, 4, 5.
• Сумма: 9 + 1 + 4 + 5 = 19.

Ответ

Обходите дерево по уровням и заново вычисляйте сумму каждого уровня. Последняя полученная сумма — сумма самых глубоких листьев: узлы максимальной глубины не имеют детей.

Предполагается узел с полями val, left и right:

def deepest_leaves_sum(root):
    if root is None:
        return 0
    level = [root]
    total = 0
    while level:
        total = sum(node.val for node in level)
        level = [child for node in level
                 for child in (node.left, node.right)
                 if child is not None]
    return total

Время O(n), память O(w), где w — максимальная ширина. Первый пример даёт 15, второй 19. Во втором пояснении ошибка: при стандартном level-order представлении узлы 9, 1, 4, 5 находятся на глубине 3 рёбра, то есть на четвёртом уровне.