一次只建立一个级别，例如：
class Node(object):
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
def traverse(rootnode):
thislevel = [rootnode]
while thislevel:
nextlevel = list()
for n in thislevel:
print n.value,
if n.left: nextlevel.append(n.left)
if n.right: nextlevel.append(n.right)
print
thislevel = nextlevel
t = Node(1, Node(2, Node(4, Node(7))), Node(3, Node(5), Node(6)))
traverse(t)
：如果您希望在最大消耗的“辅助”内存中节省少量费用（永远不要在该“辅助”内存中同时拥有所有此级别和下一个级别），那么您当然可以使用collection.deque代替list，并消耗当前（通过popleft）进行平移，而不是简单地循环。一次创建一个级别的想法（随着您消耗或迭代前一个级别）保持不变- 当您确实需要区分级别时，它比使用单个大双端队列和辅助信息更直接（例如深度或给定级别中剩余的节点数）。
但是，仅附加到列表（并在其上循环而不是“消耗”）的列表比双端队列的效率要高得多（并且如果您使用的是C ++解决方案，则类似地，std :: vector仅push_back用于构建它，然后使用它的循环比std :: deque效率更高。由于所有产生都首先发生，然后是所有迭代（或消耗），因此， 内存受到严格限制，一个有趣的替代方法可能是使用列表来表示每个级别，然后.reverse在开始使用它（通过.pop调用）之前使用它- 我没有周围的大树可以通过测量进行检查，但是我怀疑这种方法仍会比实际上更快（并且实际上消耗更少的内存）deque（假设列表[[或std :: vector]]的基础实现实际上在对pop[[或pop_back]]的几次调用之后确实回收了内存-当然，对于双端队列也有相同的假设；-）。
602392714
清零编程群