Binary Tree Maximum Path Sum

Сложная№124узлы дерева

Дан корень двоичного дерева, значения в узлах бывают отрицательными. Путь идёт от узла к узлу по рёбрам, заходит в каждый узел не больше одного раза и содержит хотя бы один узел; через корень он идти не обязан. Нужно найти наибольшую сумму значений на пути. Наше дерево: -5 с потомками 3 и 6; у 3 потомки 7 и 9; у 9 левый потомок -4; у 6 правый потомок -1. Ответ 19: путь 7 → 3 → 9.

124 Binary Tree Maximum Path SumРазбор · 1×

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

best = -∞nonenonenonenonenonenonenonenone-53679-1-4стек вызововвершина справа—
не посещёнждёт в стеке вызововтекущий вызовпуть, который взвешиваем, или лучший покавернул, ↑ лучшая ветка внизотрицательная ветка, отброшена

best = -∞: значения бывают отрицательными, поэтому первый путь должен победить при любой сумме

01/61
сначала · назад · пуск · шаг
Скорость
1function maxPathSum(root):
2 best = -infinity // shared by every call of gain
3 gain(root)
4 return best
5
6function gain(node):
7 if node is none:
8 return 0
9 left = max(gain(node.left), 0) // drop a negative branch
10 right = max(gain(node.right), 0)
11 best = max(best, left + node.val + right)
12 return node.val + max(left, right)
состояние
best
-∞
node
–
left
–
right
–
нажмите шаг, чтобы вернуться

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

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

  1. У каждого пути есть одна самая высокая вершина, где он поворачивает: поднимается с одной стороны и спускается с другой. Поэтому достаточно попробовать каждый узел в роли такой вершины с лучшей веткой вниз с каждой стороны.
  2. Ветка с отрицательной суммой только портит путь, поэтому max(gain, 0) её отбрасывает, и путь просто заканчивается в узле.
  3. Родителю уходит только одна сторона: путь через родителя, который спустился сюда, не может разойтись в обе ветки. Сумма с двумя сторонами идёт в best.

Сложность

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

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

Решить на LeetCode ↗

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