Trouver le chemin le plus long entre le nœud racine et n'importe quel enfant

Question

J'ai un tableau d'éléments, dont certains ont des enfants, qui ont des enfants à leur tour et ainsi de suite. Je connais les enfants directs de chaque élément, et j'ai une liste de tous les descendants pour chaque élément.

-(NSMutableArray *)descendents:(Element *)e { 

    NSMutableArray * descendents = [NSMutableArray new]; 
    for (NSString * uID in e.children){ 
     [descendents addObject:uID]; 
     Element * k = elements[uID][@"element"]; 
     [descendents addObjectsFromArray:[self descendents:k]]; 
    } 
    return descendents; 
} 

Je peux déterminer l'élément racine en comparant le nombre total de descendants pour chaque élément. Je peux trouver le plus court chemin entre la racine et un élément donné donné ceci:

-(int)find:(NSString *)uniqueID forElement:(Element *)e { 

    int distance = 0; 
    if ([e.children containsObject:uniqueID]){ //immediate child 

     distance ++; //increment distance 
     return distance; //return 

    } else if ([e.descendents containsObject:uniqueID]){ //grand child etc 

     distance ++; 
     for (NSString * uID in e.children){ 
      Element * k = elements[uID][@"element"]; 
      distance += [self find:uniqueID forElement:k]; 
      return distance; 
     } 
    } 

    return 0; 
} 

Ce que je veux faire est de trouver la plus longue distance entre un élément et la racine. Je pense à remonter l'arbre à partir d'éléments sans enfants ou à ajouter un tableau de distances entre les éléments de la fonction de mappage. Luttant pour l'approche la plus propre - des idées?

EDIT: solution basée sur la réponse de user3290797 ci-dessous, suivi de référence au nombre maximum de les parents:

-(int)parentHeight:(NSString *)uID { 

    int maxHeight = 0; 
    Element * e = elements[uID][@"element"]; 
    for (NSString * parentID in e.parents){ 
     int height = [self parentHeight:parentID]; 
     maxHeight = (height > maxHeight) ? height : maxHeight; 
    } 
    return maxHeight + 1; 
} 

Answer 1

T La distance la plus longue entre un élément et la racine est appelée hauteur (ou profondeur) de l'arbre.

Une façon de le trouver est de parcourir récursivement l'arbre et de calculer la hauteur de chaque nœud comme le maximum des hauteurs de ses enfants plus un.

En pseudocode:

function height(node) { 
    maxChildHeight = 0 
    for(child in node.children) { 
     h = height(child) 
     if(h > maxChildHeight) { 
      maxChildHeight = h 
     } 
    } 
    return maxChildHeight + 1 
} 

Answer 2

Si pas beaucoup de noeuds, calculer chaque distance et assigner un ID pour chacun, puis vérifier le plus long d'entre eux, c'est lent mais fonctionne hahaha