ios - 查找根节点和任何子节点之间的最长路径

Question

我有一个元素数组，其中一些元素有 child ，依次类推。我知道每个元素的直接子元素，并且有每个元素的所有后代的列表。

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

我可以通过比较每个元素的后代总数来确定根元素。鉴于此，我可以找到根和任何给定元素之间的最短路线:

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

我想做的是找到元素与根之间的最长 距离。我正在考虑从子元素为零的元素返回树，或者在映射函数中的元素之间添加一个距离数组。为最干净的方法而苦苦挣扎 - 有什么想法吗？

编辑:基于以下 user3290797 的答案的解决方案，跟踪对 parent 最大数量的引用:

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

元素与根之间的最长距离称为树的高度(或深度)。

找到它的一种方法是递归遍历树并计算每个节点的高度为其子节点高度的最大值加一。

在伪代码中:

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