如何在非二叉树中找到一个节点的深度/层级？

Question

我有一棵树形结构，每个节点可以有无限的子节点，它模拟了博客的评论。

我正在尝试找出给定特定评论的ID后，该评论在树中所处的深度/级别。

我正在遵循这篇关于二叉树的指南，但是当我将其适应为非二叉树时遇到了一些问题。

以下是我迄今为止的尝试（使用Swift）：

func commentLevelRecursive(comment: Comment, commentID: String, currentLevel: Int) -> Int {
    if comment.identifier == commentID {
        return currentLevel
    }

    var newLevel = currentLevel

    for reply in comment.replies {
        newLevel = commentLevelRecursive(reply, commentID: commentID, currentLevel: currentLevel + 1)
    }

    return newLevel
}

但是它似乎总是返回1。我认为这是因为newLevel总是从0增加到1然后返回。

有人能给我一些见解，告诉我哪里出了问题吗？

- Doug Smith

---

newLevel = max(newLevel, commentLevelRecursive(reply, commentID: commentID, currentLevel: currentLevel + 1)) 新层级 = max（新层级，commentLevelRecursive(reply，commentID：commentID，currentLevel：currentLevel + 1)） - Mark

@IonescuRobert 为什么要使用max函数？这个ID只有一个节点。 - Doug Smith

是的，但您要经历多个回复，因此希望从所有回复中获得最大深度。在这种情况下，“newLevel”将是每个层级其子代的最大深度。因此，如果您遵循该规则，则在第一个节点上将具有最大深度。 - Mark

@IonescuRobert 这会对上面的代码有什么影响？如果我在for循环中替换newLevel设置，它不会输出正确的值。 - Doug Smith

哦，抱歉，我读错了。你必须每次检查是否找到了节点。让你的函数这样做：如果找不到它，则返回0；如果找到它，则返回级别。在for循环中，每次询问commentLevelRecursive(reply, commentID: commentID, currentLevel: currentLevel + 1)是否为0，如果是，则继续for循环，如果不是，则返回该值，因为你找到了答案。在for循环之后，你总是返回0。如果你在那里，那是因为你在for循环中找不到commendId，所以你返回0。抱歉误导你了:( - Mark

Answer 1

二叉树是一种特殊情况，每个节点只有两个子节点。 用于查找节点层级的方法可以扩展到普通树。

思路是相同的：

level(P) = max(level(C) for each child node C of P)+1

- squid

---

这将如何在我的代码中运作？还是需要从头开始重新设计？ - Doug Smith

这不是用于查找树的最大深度吗？ - Doug Smith

Answer 2

int MaxDepth(int x,int parent){
    int mx = 0;
    for(int  i = 0;i < graph[x].size();i++)
        if(graph[x][i]!=parent){
            mx = max(MaxDepth(graph[x][i],x),mx);
        }
        return mx + 1;
}

- Abdullah Abdelmonem