Hello les grinders,
Aujourd’hui on se retrouvait pour un problème de notre arc “Arbre” pour le problème 124. Binary Tree Maximum Path Sum 🔗, un problème classé difficile sur Leetcode, que l’on peut considérer comme un classique (6000+ upvotes & ~1.5M de soumissions).
L’énoncé
Un chemin dans un arbre binaire est une séquence de nœuds où chaque paire de nœuds adjacents de la séquence sont liés. Un nœud ne peut apparaître qu'une seule fois dans la séquence. Notez que le chemin n'a pas besoin de passer par la root de l’arbre.
La valeur d'un chemin est la somme des valeurs des nœuds dans le chemin.
Étant donné la racine d'un arbre binaire, retournez la valeur du chemin ayant la valeur maximale.
La résolution
On peut intuiter qu’une solution structurée de manière récursive, utilisant la propriété binaire de l’arbre donné, pourra nous apporter plusieurs éléments de réponses.
Cependant, plusieurs considérations sont à prendre en compte. En se basant sur ce post dans le Discuss de la question, écrit par arkaung, voici les cas à ne pas oublier:
Si l’arbre est un seul noeud, la réponse sera la valeur de ce noeud, peut importe si positive ou négative.
Pour un arbre avec 2 noeuds, cela se complexifie: Si les 2 noeuds sont positifs, il suffit de retourner la somme des 2 valeurs. Cependant si un des 2 noeuds ou les 2 sont négatifs, cela ne s’applique pas:
En effet, si un des 2 noeuds est négatif et l’autre positif, on souhaite uniquement garder le positif. Si les 2 sont négatifs, on garde le plus grand des 2.
Si le noeud sur lequel on arrive n’existe pas, on retourne 0. Cela ne changera pas en effet la valeur de la somme du reste du chemin.
Pour un arbre avec uniquement des noeuds négatifs, la réponse sera la valeur du plus grand noeud dans l’arbre. En effet, si on ajoute la valeur de n’importe quel autre noeud, la somme résultante sera plus petite et donc fausse.
💡 Voici la clé de ce problème: lorsque nous regardons les branches gauche et droite d'un nœud, on se préoccupe uniquement des gains positifs que nous pouvons récolter. C’est à dire que si la somme des valeurs de la branche droite ou gauche du noeud est inférieure à 0, cela ne nous sera pas utile pour la réponse. On compare ainsi avec 0 la somme que l’on obtient de la branche droite ou gauche.
Voici le code implémentant cet algorithme:
class Solution: | |
def maxPathSum(self, root: TreeNode) -> int: | |
self.max_path_sum = float('-inf') # force update at least once | |
def recurse(root: TreeNode) -> int: | |
if not root: return 0 # base case | |
left_sum, right_sum = max(0, recurse(root.left)), max(0, recurse(root.right)) # only care about positive gains | |
self.max_path_sum = max(self.max_path_sum, left_sum + root.val + right_sum) | |
return root.val + max(left_sum, right_sum) | |
recurse(root) | |
return self.max_path_sum |
Lorsque que nous explorons l’arbre, nous mettons à jour la variable
max_path_sum
, qui est la valeur que l’on retourne à la fin. On initialise cette variable avecfloat('-inf')
: comme cette valeur initiale est plus petite que n’importe quel noeud dans l’arbre, cette variable sera mise à jour au moins une fois - ce qui couvre le cas spécial d’un arbre avec un seul noeud.Enfin, Il est important de comprendre la différence entre la recherche du chemin avec valeur maximale contenant le nœud actuel, et ce que nous retournons pour le nœud lorsque nous récursons sur la call stack. La line 8 du code ci-dessous met ainsi
max_path_sum
à jour avec le chemin actuel, et la ligne 9 ne retourne que la valeur du chemin valide pour le noeud parent - ce chemin ne peut pas contenir les 2 enfants.
Voici le walkthrough en vidéo 👇
Encore merci à arkaung pour sa solution très détaillée.
Le reste de la forêt
La semaine prochaine, on continue sur notre arc “Arbre” avec le problème 968. Binary Tree Cameras 🔗
As usual, rendez-vous 09:30am Paris time samedi prochain sur notre Twitch pour faire cet exercice ensemble 😎
A samedi prochain!
Your friends at LeetGrind,