Максимальная сумма пути в бинарном дереве
Published: 2023-08-14 21:07:58

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

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

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/l04924nlw7dde7sqnslo.png)

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

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

## Решение.

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

Мое описание обхода бинарного дерева: [Обход Бинарного Дерева](https://dev.to/faangmaster/alghoritmy-obkhoda-dvoichnogho-dierieva-26l4).

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

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

```

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

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

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

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

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

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/hv51zl9zebbvwpryzlv9.png)

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

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/a226vymsiy5ca1y48mcn.png)

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

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/igot2iy8s5vf9o5zd536.png)

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

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/e56y5gx17fjibvks01o2.png)

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

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/1c30b5la6h5ifie9hxne.png)

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

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/4tawg8wizkpru3uckam3.png)

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

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

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/1eggx1rcmd2vok5tr0ca.png)

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


```java
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:

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/2bqn4nk342res3sah5n1.png)

Вначале наша рекурсивная функция погрузится максимально влево, для тривильных 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.

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/nt8ucafd2639rblvzvnb.png)

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


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/oy4d1kkiaq72qyyey0qi.png)



![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/2jlhqdz3g0wj0x1cft98.png)

Для вершины 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:

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/3ewq3zn32mr81t4n5r38.png)

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


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/fq8igcwfxof1vn7gi7uw.png)