Как вычислить максимальный вес пути в дереве

Что проверяют

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

Как отвечать

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

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

• выгода ветки: что узел отдаёт родителю, node.val + Math.max(0, Math.max(left, right)). Вверх путь может продолжиться только через одну ветку;
• лучший путь через узел: node.val + Math.max(0, left) + Math.max(0, right). Здесь склеиваются обе ветки, и результат обновляет глобальный максимум;
• отсечение отрицательных: Math.max(0, ...) означает, что убыточную ветку выгоднее не брать вовсе.

Глобальный максимум инициализируйте Long.MIN_VALUE или весом корня, а не нулём: если все веса отрицательные, ответ это наименее отрицательный узел. Сумму держите в long, если веса большие. Для n-арного дерева берутся две лучшие положительные выгоды среди детей.

Сложность O(n) по времени и O(h) по памяти на стек вызовов. На вырожденном дереве в сотни тысяч узлов рекурсия упадёт с StackOverflowError, поэтому стоит упомянуть итеративный вариант: постфиксный обход через ArrayDeque и HashMap с выгодами уже посчитанных узлов.

Где спотыкаются

Не уточняют задачу и решают вариант «от корня до листа», когда спрашивали про любой путь. Решение выглядит рабочим, но на тестах интервьюера расходится.

Возвращают родителю сумму обеих веток. Такой «путь» раздваивается и перестаёт быть путём, ответ получается завышенным.

Стартуют максимум с нуля. На дереве из одних отрицательных весов функция вернёт 0, которого в дереве нет, и это первое, что интервьюер проверит.