Функция для поиска самого длинного пути в двоичном дереве

Python Сложный functions

Задача «Функция для поиска самого длинного пути в двоичном дереве»

Дано двоичное дерево, каждый узел которого содержит целое число. Необходимо найти максимальную сумму значений на пути от корня до листа. Путь должен начинаться в корне и заканчиваться в листе. Напишите функцию max_path_sum(root), которая принимает корень дерева и возвращает максимальную сумму. Дерево задаётся в виде списка, где -1 означает отсутствие узла. Ограничения: количество узлов не более 1000, значения узлов от -1000 до 1000.

Формат ввода

В первой строке целое число n — количество узлов. Во второй строке n целых чисел через пробел — значения узлов в порядке обхода в ширину (уровень за уровнем), где -1 означает пустой узел.

Формат вывода

Одно целое число — максимальная сумма на пути от корня до листа.

Примеры

Пример 1

ВВОД

5
-1 2 3 -1 -1

ВЫВОД

2

main.py