Вопрос

Вам дан root двоичного дерева, содержащего только цифры от 0 до 9.

Каждый путь от корня к листу в дереве представляет собой число.

  • Например, путь от корня к листу 1 -> 2 -> 3 представляет число 123.

Возвращает общую сумму всех корневых чисел. Тестовые случаи генерируются таким образом, чтобы ответ соответствовал 32-разрядному целому числу.

Узел конечный — это узел без дочерних элементов.

Пример 1:

Input: root = [1,2,3]
Output: 25
Explanation:
The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.
Therefore, sum = 12 + 13 = 25.

Пример 2:

Input: root = [4,9,0,5,1]
Output: 1026
Explanation:
The root-to-leaf path 4->9->5 represents the number 495.
The root-to-leaf path 4->9->1 represents the number 491.
The root-to-leaf path 4->0 represents the number 40.
Therefore, sum = 495 + 491 + 40 = 1026.

Ограничения:

  • Количество узлов в дереве находится в диапазоне [1, 1000].
  • 0 <= Node.val <= 9
  • Глубина дерева не будет превышать 10.

Решение Java

Временная сложность приведенного ниже решения
O(n), мы посещаем каждый узел дерева.

Код