我对Algo&DS的理解有点新手。我不确定这是一个重复的或相关的问题,还是完全微不足道。无论我在哪里看到级别顺序遍历或BFS被提到,我都看到使用了一个队列。我无法理解这其中的复杂性,在空间方面,更重要的是时间复杂性,与使用字典实现的相反。在
def getLevelElements(tree, level=0, cont={}):
"""Get mapping of level and elements in a level
:param tree: Input tree, ex.
1
2
4
5
8
9
3
6
7
10
None
:return: {0: [1], 1: [2, 3], 2: [4, 5, 6, 7], 3: [8, 9, 10]}
"""
if tree is not None:
cont.setdefault(level, []).append(tree.root)
if tree.leftChild is not None:
getLevelElements(tree.leftChild, level + 1, cont)
if tree.rightChild is not None:
getLevelElements(tree.rightChild, level + 1, cont)
return cont
def levelOrderTraversalOut(tree):
levelElementsMap = getLevelElements(tree)
out = []
for elements in levelElementsMap.values():
out += elements
return out
我的要求是使用级别顺序遍历来获取列表中树的元素。在
如果我理解正确,你需要一个BFS顺序的树元素。 我建议smth这样:
相关问题 更多 >
编程相关推荐