Вам дан root
двоичного дерева, содержащего только цифры от 0
до 9
.
Каждый путь от корня к листу в дереве представляет собой число.
- Например, путь от корня к листу
1 -> 2 -> 3
представляет число123
.
Возвращает общую сумму всех корневых чисел. Тестовые случаи генерируются таким образом, чтобы ответ соответствовал 32-разрядному целому числу.
Узел конечный — это узел без дочерних элементов.
Пример 1:
Input: root = [1,2,3] Output: 25 Explanation: The root-to-leaf path1->2
represents the number12
. The root-to-leaf path1->3
represents the number13
. Therefore, sum = 12 + 13 =25
.
Пример 2:
Input: root = [4,9,0,5,1] Output: 1026 Explanation: The root-to-leaf path4->9->5
represents the number 495. The root-to-leaf path4->9->1
represents the number 491. The root-to-leaf path4->0
represents the number 40. Therefore, sum = 495 + 491 + 40 =1026
.
Ограничения:
- Количество узлов в дереве находится в диапазоне
[1, 1000]
. 0 <= Node.val <= 9
- Глубина дерева не будет превышать
10
.
Решение Java
Временная сложность приведенного ниже решения
O(n), мы посещаем каждый узел дерева.