algorithm - 如何找到非二叉树中节点的深度/级别？

Question

我有一个树结构，其中每个节点基本上可以有无限个子节点，它正在为博客的评论建模。

根据特定评论的 ID，我试图找出该评论在树中的深度/级别。

我正在关注 this guide that explains it for binary trees ，但是在将其改编为非二叉树时，我遇到了一些麻烦。

这是我目前的尝试(在 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 然后返回。

谁能告诉我哪里出错了？

Answer 1

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

思路是一样的:

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