Максимальная сумма пути в бинарном дереве

Задача.

Дано бинарное дерево. Путь в бинарном дереве — это последовательность вершин, в которой каждая пара соседних вершин в последовательности имеет соединяющее их ребро. Вершина может появиться в последовательности не более одного раза. Путь не обязательно должен проходить через корень. Сумма пути — это сумма значений вершин в пути. Необходимо найти максимальную сумму среди всех непустых путей.

Например, для дерева

Ответ 42. Это сумма пути 15 + 20 + 7

Ссылка на leetcode: https://leetcode.com/problems/binary-tree-maximum-path-sum/description/

Решение.

Как я уже описывал ранее, если у нас в задаче дано бинарное дерево (нет указаний на то, что это бинарное дерево поиска), то решение почти в 100% случаев это просто применение алгоритма обхода бинарного дерева. Эта задача не исключение.

Мое описание обхода бинарного дерева: Обход Бинарного Дерева.

Код алгоритма обхода дерева post-order выглядит следующим образом (что является просто упрощением поиска в глубину для бинарных деревьев):

public static void dfs(BinaryTree tree) {
  if (tree == null) {
    return;
  }
  dfs(tree.left);
  dfs(tree.right);
  visit(tree);
}

При условии, что код класса BinaryTree следующий:

class BinaryTree {
  public int value;
  public BinaryTree left;
  public BinaryTree right;

  public BinaryTree(int value) {
    this.value = value;
  }
}

Хорошо. Теперь давайте посмотрим, что нам надо написать вместо visit и что нам надо возвращать и передавать в функцию.

Давайте рассмотрим это для вершины 20 в дереве из нашего примера:

У вершины 20 есть два тривиальных поддерева с вершиной 15 слева и 7 справа. Пусть наша функция возвращает максимальную сумму пути для левого поддерева и проходящая через нашу вершину 20 и для правого поддерева и также проходящая через нашу рассматриваемую вершину. Пока мы не знаем как выглядит наша функция, но пока очевидно, что значение для левого поддерева будет 15, а для правого 7.

Тогда для нахождения максимальной суммы пути, который проходит через вершину 20, нам надо рассмотреть путь 15->20 и дальше возможно уходит наверх:

Пути 7->20 и дальше возможно уходит наверх:

Пути, который выходит из левого поддерева, проходит через нашу вершину 20 и уходит в правое поддерево:

Или же только состоит из нашей вершины и возможно уходит наверх (например если слева и справа какие-то отрицательные числа):

Если мы по мере обхода дерева будет обновлять некую глобальную переменную max, текущей найденной максимальной суммой, то в качестве результата функции нам надо возвращать другое значение. Максимальную сумму пути, который возможно уходит наверх. Т.е. из возвращаемого значения надо исключить вариант когда путь выходит слева, проходит через вершину и уходит вравое поддерево. Он, очевидно, не будет уходить наверх. Такой случай будем учитывать только для обновления глобальное переменной с максимумом пути.

Т.е. для вершины 20 возвращаемое значение это 35 (путь 15->20->..), т.к. мы не рассматриваем путь 15->20->7 т.к. он не может уходить наверх. Но в качестве максимального пути результат будет 42. Это как раз путь 15->20->7.

Код решения с комментариями:

class Solution {
    int max;

    public int maxPathSum(TreeNode root) {
        max = Integer.MIN_VALUE;
        helper(root);
        return max;
    }

    private int helper(TreeNode node) {
        if (node == null) {
            return 0;
        }
        //Максимум для левого поддерева
        int left = helper(node.left);
        //Максисмум для правого поддерева
        int right = helper(node.right);
        //result - максимум из 3 случаев:
        //1) left->node->
        //2) right->node->
        //3) node->
        int result = Math.max(left, right) + node.val;
        result = Math.max(result, node.val);
        //При этом для рассчета максимального пути нужно рассмотреть 4 случай: left->node->right
        max = Math.max(max, Math.max(result, left + right + node.val));
        return result;
    }
}

Посмотрим как будет работать решение по шагам для дерева из примера. Я отобразил также null вершины и текущее значение max инициализируем минус бесконечностью или для Java подойдет Integer.MIN_VALUE:

Вначале наша рекурсивная функция погрузится максимально влево, для тривильных null вершин функция вернет 0. Далее погрузится вправо для вершины 9. Т.е. для вершины 9: left = 0, right = 0.
Тогда result = Math.max(0, 0) + 9 = 9, result = Math.max(result, 9) = Math.max(9, 9) = 9.
Также обновим значение max = Math.max(Integer.MIN_VALUE, 9) = 9.

Аналогично для вершин 15 и 7:

Для вершины 20 более интересно.
left = 15
right = 7
result = Math.max(15, 7) + 20 = 35
result = Math.max(result, 20) = Math.max(35, 20) = 35. Т.е. путь 15->20->..
При этом max = Math.max(max, Math.max(35, 15 + 20 +7)) = Math.max(15, 42) = 42:

Ну и для корня: