Нахождение наибольшей суммы пути в бинарном дереве при единственном посещении узлов

Условие

Требуется реализовать функцию, которая вычисляет максимальную сумму узлов вдоль любого пути, при условии, что каждый узел может быть пройден не более одного раза. Путь может начинаться и заканчиваться в любых вершинах дерева — не обязательно от корня к листу. На приведённом ниже примере максимальная сумма достигается по пути 5 → -3 → 20, дающему 30.

    (-10)
     /
  (9)   (20)
       /   \
    (-3)   (8)
     /     / \
  (5)  (-4)  (-2)
   /
(-2)

function getMaxPathSum(root) {}

Ответ

На каждом узле вычислите лучший нисходящий путь и обновите общий максимум суммой двух полезных ветвей. В примере путь 5 → −3 → 20 даёт 22; сумма 30 получается при добавлении вершины 8.

function getMaxPathSum(root) {
  if (!root) return null;
  let best = -Infinity;
  function visit(node) {
    if (!node) return 0;
    const left = Math.max(0, visit(node.left));
    const right = Math.max(0, visit(node.right));
    best = Math.max(best, node.value + left + right);
    return node.value + Math.max(left, right);
  }
  visit(root);
  return best;
}

Выбран формат узла {value,left,right}. Родителю возвращается только одна ветка, иначе путь разветвился бы; общий максимум может соединять обе через текущий узел. Отрицательные ветви отсекаются, но при всех отрицательных значениях выбирается наибольший одиночный узел. Время O(n), стек O(h); для очень глубокого дерева нужен итеративный postorder.