Условие задачи

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

Сумма пути - это сумма значений узлов на пути.

Нужно написать функцию, которая принимает на вход корень бинарного дерева и возвращает максимальную сумму пути.

Функция должна принимать один аргумент - корень бинарного дерева, который представлен в виде класса TreeNode. Класс TreeNode имеет следующие свойства:

• val - значение, хранящееся в узле.
• left - ссылка на левое поддерево.
• right - ссылка на правое поддерево.

Примеры

Пример 1

Дано бинарное дерево:

   1
  / \\\\
 2   3

Input: root = [1,2,3]
Output: 6
Explanation: Максимальная сумма пути проходит через узел 1 (сумма пути: 2 + 1 + 3 = 6).

Пример 2

Дано бинарное дерево:

   -10
   / \\\\
  9  20
    /  \\\\
   15   7

Input: root = [-10,9,20,null,null,15,7]
Output: 42
Explanation: Максимальная сумма пути проходит через узлы: 15, 20, 7 (сумма пути: 15 + 20 + 7 = 42).

Решение

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

1. Начинаем с корня дерева.