Funktion zum Finden des längsten Pfades in einem binären Baum

Python Hard functions

Aufgabe «Funktion zum Finden des längsten Pfades in einem binären Baum»

Gegeben ist ein binärer Baum, dessen jeder Knoten eine ganze Zahl enthält. Es ist die maximale Summe der Werte auf einem Pfad von der Wurzel zu einem Blatt zu finden. Der Pfad muss an der Wurzel beginnen und an einem Blatt enden. Schreiben Sie die Funktion max_path_sum(root), die die Wurzel des Baumes entgegennimmt und die maximale Summe zurückgibt. Der Baum wird als Liste angegeben, wobei -1 das Fehlen eines Knotens bedeutet. Einschränkungen: Die Anzahl der Knoten beträgt maximal 1000, die Knotenwerte liegen zwischen -1000 und 1000.

Eingabeformat

In der ersten Zeile eine ganze Zahl n — die Anzahl der Knoten. In der zweiten Zeile n ganze Zahlen, durch Leerzeichen getrennt — die Werte der Knoten in der Reihenfolge der Breitensuche (Ebene für Ebene), wobei -1 einen leeren Knoten bedeutet.

Ausgabeformat

Eine ganze Zahl — die maximale Summe auf dem Pfad von der Wurzel zu einem Blatt.

Beispiele

Beispiel 1

EINGABE

5
-1 2 3 -1 -1

AUSGABE

2

main.py