这是我的节点定义:
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())
它在某些情况下有效,但在许多情况下给出了错误的答案。我不明白我在哪里遗漏了这个概念?
最佳答案
正如@pfctgeorge 所建议的,我根据节点值附加了级别,但是可以有多个具有相同值的节点,因为它是一棵树,在这种情况下它会给出错误的答案。
关于python - 如何使用 bfs 找到 n 叉树的最大深度?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/52177162/