ルートノードと任意の子の間の最長のパスを見つける

Question

私は要素の配列を持っています。その要素のうちのいくつかは子を持ち、順番に子を持っています。私は各要素の直接の子を知っていて、各要素のすべての子孫のリストを持っています。

各要素の子孫の合計数を比較することで、ルート要素を判断できます。私はルートや、これを与えられた任意の要素との間の最短ルートを見つけることができます。

-(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; 
} 

私は何をしたい要素と根の間最長距離を見つけることです。私はゼロの子を持つ要素からツリーをバックアップするか、マッピング関数の要素間に距離の配列を追加することを考えています。最もクリーンなアプローチ - あらゆるアイデアに苦しんでいますか？

EDIT：以下user3290797の回答に基づいて ソリューション、両親の最大数への参照を追跡：

-(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要素と根との間の最長距離は、木の高さ（または深さ）と呼ばれます。

これを見つけるには、ツリーを再帰的に横断して、すべてのノードの高さを子の高さの最大値+ 1として計算する方法があります。擬似コードで

：

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

Answer 2

ノードのない多くは、それぞれの距離を計算して割り当てた場合それぞれのIDは、それらの最長をチェックしてください、これは遅いですが、ハハハです