Sum Root to Leaf Numbers

Средняя№129сверху вниз

Дан корень двоичного дерева, в узлах которого цифры от 0 до 9. Каждый путь от корня вниз до листа записывает число: 1 → 4 → 6 — это 146. Нужно вернуть сумму всех таких чисел. Наше дерево: 2 с потомками 7 и 5; у 7 потомки 3 и 0, у 5 только правый потомок 8. Пути дают 273, 270, 258 — ответ 801.

129 Sum Root to Leaf NumbersРазбор · 1×

Пример: сложить числа, которые записаны путями от корня до листьев: каждый вызов дописывает свою цифру к числу, полученному сверху, и передаёт его дальше вниз.

275308числа в листьях—стек вызововвершина справа—
ещё не посещённа пути, ждёттекущий вызов, рядом его числовернул ответ

Начинаем с корня 2 и пустого числа: walk(2, 0)

01/38
сначала · назад · пуск · шаг
Скорость
1function sumNumbers(root):
2 return walk(root, 0)
3
4function walk(node, number):
5 number = number * 10 + node.val
6 if node.left is none and node.right is none:
7 return number
8 total = 0
9 for each child of node that is not none:
10 total = total + walk(child, number)
11 return total
состояние
root
2
node
–
number
–
total
–
нажмите шаг, чтобы вернуться

← → шаг · пробел — пауза

Почему это работает

  1. Дописать цифру — это number × 10 + val: уже записанные цифры сдвигаются на разряд влево. Так каждый узел получает ровно то число, которое записано путём над ним, вместе со своей цифрой.
  2. Число готово только в листе, поэтому своё число возвращает только лист. Внутренний узел, как 5, возвращает лишь то, что вернули потомки, и 25 в сумму не попадает.
  3. Каждый вызов возвращает сумму чисел своего поддерева, поэтому корень возвращает сумму всех чисел.

Сложность

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

дальшеТеперь реши её сам, без подсказок.

Решить на LeetCode ↗

Задача и её условие принадлежат LeetCode. Здесь — наш пересказ, наш пример и наше решение. Patterns Hero не связан с LeetCode.