Étant donné un arbre générique composé de N nœuds, la tâche consiste à trouver la somme maximale du chemin de la racine au nœud feuille.
Exemples:
Saisir:
Sortir: 12
Explication: La somme du chemin vers chaque feuille à partir de la racine est :
Pour le nœud 4 : 1 -> 2 -> 4 = 7
Pour le nœud 5 : 1 -> 2 -> 5 = 8
Pour le nœud 6 : 1 -> 3 -> 6 = 10
Pour le nœud 7 : 1 -> 3 -> 7 = 11
Pour le nœud 8 : 1 -> 3 -> 8 = 12 (maximum)
La somme de chemin maximale est de 12, c’est-à-dire de la racine 1 à la feuille 8.
Approcher: Le problème donné peut être résolu en effectuant la traversée DFS sur l’arbre donné. L’idée est d’effectuer la traversée DFS à partir du nœud racine de l’arbre générique donné en gardant la trace de la somme des valeurs des nœuds dans chaque chemin et si un nœud feuille se produit, maximiser la valeur de la somme actuelle des chemins obtenue dans un variable, disons somme max.
Après avoir effectué le DFS Traversal, imprimez la valeur de somme max comme chemin de somme maximum résultant.
Vous trouverez ci-dessous la mise en œuvre de l’approche ci-dessus :
C++
|
#include en utilisant l’espace de noms std ; struct Noeud { valeur int; vecteur } ; Node* newNode(int key) { Nœud* temp = nouveau nœud ; temp->val = clé; température de retour ; } void DFS(Node* root, int sum, int& ans) { if (root->child.size() == 0) { ans = max(ans, somme); revenir; } pour (entier i = 0 ; i < root->child.size(); i++) { DFS(racine->enfant[i], somme + racine->enfant[i]->val, ans); } } int main() { Nœud* racine = nouveauNœud(1) ; (root->child).push_back(newNode(2)); (root->child).push_back(newNode(3)); (racine->enfant[0]->enfant).push_back(newNode(4)); (racine->enfant[1]->enfant).push_back(newNode(6)); (racine->enfant[0]->enfant).push_back(newNode(5)); (racine->enfant[1])->child.push_back(newNode(7)); (racine->enfant[1]->enfant).push_back(newNode(8)); int maxSumPath = 0; DFS(racine, racine->val, maxSumPath); cout << maxSumPath; renvoie 0 ; } |
Complexité temporelle : AU)
Espace auxiliaire : O(1)
Attention lecteur ! N’arrêtez pas d’apprendre maintenant. Obtenez tous les concepts importants de DSA avec le Cours auto-rythmé DSA à un prix adapté aux étudiants et devenez prêt pour l’industrie. Pour compléter votre préparation de l’apprentissage d’une langue à DS Algo et bien d’autres, veuillez vous référer Cours complet de préparation aux entretiens.
Au cas où vous souhaiteriez assister cours en direct avec des experts, veuillez vous référer Cours en direct DSA pour les professionnels en activité et Programmation compétitive en direct pour les étudiants.
