如何使用 bfs 找到 n 叉树的最大深度？

Question

这是我的节点定义：

class Node(object):
    def __init__(self, val, children):
        self.val = val
        self.children = children

现在我必须找到树中的最大深度。我正在使用广度优先搜索来标记每个节点的级别，然后返回级别的最大值。

这是我的代码：

def maxDepth(self, root):
    """
    :type root: Node
    :rtype: int
    """
    if(root == None):
        return 0

    q = []
    q.append(root)

    level={root.val:1}

    while(len(q)>0):

        s = q.pop(0)

        for c in s.children:
            q.append(c)
            level[c.val]=level[s.val]+1

    return max(level.values())

它在某些情况下有效，但在许多情况下给出了错误的答案。我不明白我哪里遗漏了这个概念？

Answer 1

正如@pfctgeorge 所建议的那样，我根据节点值附加了级别，但是可以有多个具有相同值的节点，因为它是一棵树，在这种情况下它会给出错误的答案。

Answer 2

既然你知道哪里出错了，你可以像下面那样做来达到树的最大深度-

伪代码：

q = []
q.offer(root)
level = 1

while q.isEmpty() == false:

    size = q.size()
    for i = 0 to size:
        curr_node = q.poll()
        for each_child in curr_node:
            q.offer(each_child)

    level = level + 1

return level

如何使用 bfs 找到 n 叉树的最大深度？

How to find max depth of n-ary tree using bfs?

python

algorithm

tree

graph-theory

breadth-first-search