Как найти максимальную глубину n-арного дерева, используя bfs?

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

Так как вы знаете, где вы ошиблись, вы можете сделать что-то вроде ниже, чтобы достичь максимальной глубины дерева-

псевдокод:

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

Answer 2

Как подсказывает @pfctgeorge, я добавлял уровень в соответствии со значением узла, но может быть несколько узлов с таким же значением, как у дерева, в этом случае он даст неправильный ответ.