Почему это работает
- У каждого пути есть одна самая высокая вершина, где он поворачивает: поднимается с одной стороны и спускается с другой. Поэтому достаточно попробовать каждый узел в роли такой вершины с лучшей веткой вниз с каждой стороны.
- Ветка с отрицательной суммой только портит путь, поэтому max(gain, 0) её отбрасывает, и путь просто заканчивается в узле.
- Родителю уходит только одна сторона: путь через родителя, который спустился сюда, не может разойтись в обе ветки. Сумма с двумя сторонами идёт в best.
Сложность
Время O(n): каждый узел посещаем один раз. Память O(h), где h — высота дерева: в стеке вызовов лежит один путь.
дальшеТеперь реши её сам, без подсказок.
Решить на LeetCode ↗