FR
RU
EN
ES
ZH
DE
PT
AR
HI
Fonction pour trouver le chemin le plus long dans un arbre binaire
Python
Hard
functions
Tâche «Fonction pour trouver le chemin le plus long dans un arbre binaire»
Étant donné un arbre binaire dont chaque nœud contient un entier. Il faut trouver la somme maximale des valeurs sur un chemin de la racine à une feuille. Le chemin doit commencer à la racine et se terminer à une feuille. Écrivez une fonction max_path_sum(root) qui prend la racine de l’arbre et retourne la somme maximale. L’arbre est donné sous forme de liste, où -1 signifie l’absence de nœud. Contraintes : le nombre de nœuds ne dépasse pas 1000, les valeurs des nœuds sont comprises entre -1000 et 1000.
Format d\ entrée
Sur la première ligne, un entier n — le nombre de nœuds. Sur la deuxième ligne, n entiers séparés par des espaces — les valeurs des nœuds dans l’ordre du parcours en largeur (niveau par niveau), où -1 signifie un nœud vide.
Format de sortie
Un entier — la somme maximale sur un chemin de la racine à une feuille.
Exemples
Exemple 1
ENTRÉE
5
-1 2 3 -1 -1
SORTIE
2
main.py