Path Sum

Лёгкая№112сверху вниз

Дан корень двоичного дерева и число target. Нужно сказать, есть ли путь от корня вниз до листа — узла без потомков, — сумма которого равна target. Наше дерево: 6 с потомками 4 и 3; у 4 только правый потомок 5, у 3 — потомки 1 и 2. target = 10 — ответ true: 6 → 3 → 1. 6 → 4 тоже даёт 10, но 4 — не лист.

112 Path SumРазбор · 1×

Пример: проверить, есть ли путь от корня до листа с суммой 10: каждый вызов вычитает своё значение и передаёт остаток вниз.

target = 10рядом — restnone643512стек вызововвершина справа6
ещё не посещённа пути, ждёттекущий вызоввернул trueвернул false

6 — узел, а не none: собрать осталось 10

01/30
сначала · назад · пуск · шаг
Скорость
1function hasPathSum(node, target):
2 if node is none:
3 return false
4 rest = target - node.val
5 if node.left is none and node.right is none:
6 return rest == 0 // only a leaf ends a path
7 if hasPathSum(node.left, rest):
8 return true
9 return hasPathSum(node.right, rest)
состояние
node
6
target
10
rest
–
нажмите шаг, чтобы вернуться

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

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

  1. Каждый вызов получает, сколько пути над ним ещё осталось собрать, поэтому листу достаточно проверить, что не осталось ничего: rest == 0.
  2. Проверка — только в листе. Ноль во внутреннем узле или в его пустом потомке не считается: путь ещё не дошёл до листа.
  3. Как только одна сторона вернула true, вызов тоже сразу возвращает true, и остальное дерево не обходим.

Сложность

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

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

Решить на LeetCode ↗

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