Función para encontrar la ruta más larga en un árbol binario

Python Hard functions

Tarea «Función para encontrar la ruta más larga en un árbol binario»

Dado un árbol binario, cada nodo contiene un número entero. Es necesario encontrar la suma máxima de valores en una ruta desde la raíz hasta una hoja. La ruta debe comenzar en la raíz y terminar en una hoja. Escriba una función max_path_sum(root) que recibe la raíz del árbol y devuelve la suma máxima. El árbol se representa como una lista, donde -1 indica ausencia de nodo. Restricciones: la cantidad de nodos no supera los 1000, los valores de los nodos van de -1000 a 1000.

Formato de entrada

En la primera línea, un número entero n — la cantidad de nodos. En la segunda línea, n números enteros separados por espacios — los valores de los nodos en orden de recorrido por niveles (nivel por nivel), donde -1 indica un nodo vacío.

Formato de salida

Un número entero — la suma máxima en una ruta desde la raíz hasta una hoja.

Ejemplos

Ejemplo 1

ENTRADA

5
-1 2 3 -1 -1

SALIDA

2

main.py