Défi: Étant donné un arbre binaire *non vide *, trouvez la somme de chemin maximale. Pour ce problème, un chemin est défini comme n’importe quelle séquence de nœuds d’un nœud de départ à n’importe quel nœud de l’arborescence le long des connexions parent-enfant. Le chemin doit contenir au moins un nœud et n’a pas besoin de passer par la racine :

Example #1:
Input: 
4
/ \
5 6
Output: 15

Exemple #2:

Input: 
-10
/ \
9 20
/ \
15 7
Output: 42

Le défi

Comme son nom l’indique, un arbre binaire est un type populaire de structure de données arborescente. Pour soutenir leur efficacité dans le temps et l’espace, les arbres sont souvent représentés par une clé et deux nœuds foliaires ou plus, similaires aux structures suivantes:

As one may guess, recursion is also a common property of tree-based structures. Même si la plupart des fonctions récursives sont mal vues dans les applications réelles, les arbres permettent certaines efficacités car chaque nœud feuille peut également représenter un autre arbre :

S’ils ne sont pas compris correctement, les arbres peuvent créer de la confusion et ajouter de la complexité. Pour résoudre notre défi de code, nous devrons concevoir une méthode cohérente pour naviguer dans notre arborescence et un moyen de comparer toutes les permutations possibles.

Travaillons à visualiser nos idées avant de les valider dans le code. Pour commencer, nous aborderons d’abord comment naviguer dans l’arborescence. Étant donné que les structures arborescentes incorporent une propriété de concept supplémentaire de *depth*, des techniques simples telles que l’énumération rapide ne sont normalement pas appliquées. Au lieu de cela, nous pouvons utiliser des algorithmes de traversée spécifiques comme la recherche en profondeur ou en largeur d’abord (par exemple, DFS et BFS respectivement). Même si le sujet de BFS est suffisamment détaillé pour une nouvelle discussion, nous pouvons conclure que ce serait la façon normale de traverser une telle structure. Cependant, puisque nous travaillons avec un arbre binaire, nous pouvons appliquer des efficacités algorithmiques spécifiques pour aider à raccourcir le processus de traversée.

Alors, qu’est-ce qu’un arbre binaire ? Il s’agit essentiellement d’un tableau standard visualisé sous forme d’arbre. Dans ce cas, l’accent est mis sur les aspects de visualisation car cela affectera la façon dont nous naviguons dans la structure. Par exemple, pour chaque nœud, ses nœuds enfants feuilles gauche et droite peuvent en fait être calculés à l’aide de ces formules simples :

Comme discuté, ces formules fonctionnent car la structure sous-jacente de notre arbre est un tableau. Cela diffère d’autres structures comme un arbre B, un Trie ou un graphique où l’on appliquerait une structure de données personnalisée spécifique pour représenter un modèle.

Faire des comparaisons

Puisque notre Arbre binaire n’est en fait rien de plus qu’un Tableau, nous pouvons en effet utiliser l’énumération de base pour parcourir toutes les valeurs. Cependant, nous appliquerons nos formules pour déterminer nos nœuds de feuilles enfants. Une fois établi, nous pouvons suivre les totaux de chaque sous-arbre en utilisant une forme simple de mémorisation (par exemple. programmation dynamique).