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

Источник: https://leetcode.com/problems/binary-tree-maximum-path-sum/

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

Сумма пути — это сумма значений вершин пути.  

Учитывая корень двоичного дерева, вернуть максимальную сумму пути любого непустого пути.

Пример 1:

Дано: root = [1,2,3]
Результат: 6
Пояснение: Оптимальный путь: 2 -> 1 -> 3 с суммой 2 + 1 + 3 = 6.

Пример 2:

Дано: root = [-10,9,20,null,null,15,7]
Результат: 42
Пояснение: Искомый путь: 15 -> 20 -> 7 с суммой 15 + 20 + 7 = 42.

Ограничения:

• Число вершин в дереве находится в диапазоне [1, 3 * 104].
• -1000 <= Node.val <= 1000

Структура данных

/**

* Definition for a binary tree node.

* struct TreeNode {

* int val;

* TreeNode *left;

* TreeNode *right;

* TreeNode() : val(0), left(nullptr), right(nullptr) {}

* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}

* };

*/

Идея решения

Поскольку нам нужно пересмотреть все пути, идущие из любого левого поддерева в любое правое поддерево, то будем искать решение методом перебора, поиском в грубину (DFS). 

Нам нужно построить функцию max_gain и найти такую вершину x, чтобы max_gain(x) = x.val+max_gain(x.left) + max_gain(x.right) было максимальным. То есть получается рекурсия, которую мы можем стартоватьс корня дерева. 

Мы создадим глобальную переменную, которую будем обновлять максимальным значением, пока не просмотрим рекурсивно все пути в дереве. На каждом рекурсивном вызове мы:

1. проверяем, чтобы вершина, которая передается в max_gain не была null. Если это так, то мы больше не можем увеличить сумму пути, поэтому возвращаем 0.
2. Если текущая вершина не null, то для этой вершины мы счиаем x.val+max_gain(x.left) + max_gain(x.right). Если значение превышает глобальную переменную, то обновляем ее.
3. Теперь нам надо выйти из рекурсии. Текущая вершина может быть частью пути для какого-то другого корня. Нам нужно максимизировать сумму пути, проходящего через тот корень. Этот путь будет содержать левое или правое поддерево текущей вершины. Мы выбираем то поддерево, которое имеет максимальную сумму, то есть x.val + max(max_gain(x.left), max_gain(x.right)).
    

Имплементация

class Solution {
  int max_sum = Integer.MIN_VALUE;

  public int max_gain(TreeNode node) {
    if (node == null) return 0; // 1. обработка пограничного случая

    // 2. рекурсивный шаг
    // считаем max_gain для левого и правого поддерева вершины node. 
    // поскольку значения в вершинах могут быть отрицательными, то сравниваем с нулем 
    int left_gain = Math.max(max_gain(node.left), 0);
    int right_gain = Math.max(max_gain(node.right), 0);

    // 3. собираем результаты рекурсии
    // считаем gain для текущей вершины node
    int price_newpath = node.val + left_gain + right_gain;

    // обновляем глобальный max_gain
    max_sum = Math.max(max_sum, price_newpath);

    // возвращаем максимальное поддерево, которое может быть частью другого пути
    return node.val + Math.max(left_gain, right_gain);
  }

  public int maxPathSum(TreeNode root) {
    max_gain(root); // вызываем функцию
    return max_sum;
  }
}