Застрял на рекурсивном проектировании состояний для зигзагообразного пути с переменной суммой в двоичном дереве ⇐ JAVA

[Anonymous]

Я пытаюсь рассуждать о рекурсивном алгоритме на деревьях и чувствую, что упускаю что-то тонкое.
У меня есть неизменяемое двоичное дерево (не BST), где каждый узел имеет значение int. Я хочу вычислить максимальный зигзагообразный путь с переменной суммой в любом месте дерева. Путь — это любой нисходящий путь (начинается с любого узла, идет только к дочерним узлам). Путь должен строго чередоваться влево/вправо на каждом шаге. В сумме чередуются знаки, начинающиеся с + в начальном узле: +v0 − v1 + v2 − v3 …. Разрешены пути с одним узлом.
Вот код, который, как я думал, должен работать, но он не работает в некоторых случаях с отрицательными значениями и когда лучший путь не начинается с корня.

Код: Выделить всё

int maxZigZagSum(Node root) {
return helper(root, true, 0);
}

int helper(Node node, boolean goLeft, int sign) {
if (node == null) return 0;

int cur = (sign == 0 ? node.val : -node.val);

int next;
if (goLeft) {
next = helper(node.left, false, 1 - sign);
} else {
next = helper(node.right, true, 1 - sign);
}

return Math.max(cur, cur + next);
}

Я дважды пытался вызвать helper в корне (один раз начиная слева, один раз справа), но это все равно не исправляет все случаи. Интуитивно я чувствую, что мне нужно отслеживать оба «последнего направления» и «четности суммы», но всякий раз, когда я добавляю больше параметров, рекурсия взрывается, и я не могу сохранить ее O(n). Я также не понимаю, как обрабатывать пути, начинающиеся в середине дерева, без перезапуска рекурсии с каждого узла, что было бы O(n²).
Какая минимальная информация должна быть возвращена от каждого рекурсивного вызова, чтобы родительский элемент мог правильно объединить результаты? Как структурировать рекурсию так, чтобы пути могли начинаться в любом узле, но при этом вы проходили дерево только один раз? Почему подход «вернуть лучший путь, начинающийся здесь» не работает без дополнительного состояния?

Подробнее здесь: https://stackoverflow.com/questions/798 ... -binary-tr