查找根节点和任何 child 之间的最长路径

Question

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

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

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

编辑： 基于 user3290797 下面的答案的解决方案，跟踪对 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

如果不是很多节点，计算每个距离并为每个分配一个ID，然后检查其中最长的一个，这很慢但是有效哈哈哈

Answer 2

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

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

在伪代码中：

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

查找根节点和任何 child 之间的最长路径

Find longest path between root node and any child

ios

objective-c

algorithm

breadth-first-search

depth-first-search