Python deque 和 popleft（集合模块的一部分）

Question

这给出了一个列表，其中包含每个根到叶的路径：

def binaryTreePaths(self, root):
    from collections import deque
    if root is None:
        return []
    queue = deque( [ [root, str(root.val)] ] )
    ans = []
    while queue:
        front, path = queue.popleft()
        if front.left is None and front.right is None:
            ans += path,
            continue
        if front.left:
            queue += [front.left, path + "->" + str(front.left.val)],
        if front.right:
            queue += [front.right, path + "->" + str(front.right.val)],
    return ans

我不明白它是如何工作的，因为假设我们有一棵 1-2-3 的树（节点 1 有左右 child）。在 while 循环后的第一行，当你弹出它时，队列再次是 deque ([ ])。由于 front 是 node1 并且 front.left 存在（因为 node1 有一个左 child），我们将 front.left 和一个字符串再次添加到队列中。

那么队列就是deque([node2, "stringhere"])。然后我们打了第三个if语句：因为node1确实有一个权利child（node3），我们再次添加到队列所以队列变成了deque（[node2，"stringhere"、节点 3、"anotherstring"]）。

然后我们返回并进入 while 循环；由于队列不为空，我们有：

front, path = queue.popleft()

我们的队列是 deque([node2, "stringhere", ndoe3, "anotherstring"]) 但不可能调用 front, path ，因为队列中有 4 个参数。

我没有得到什么？

Answer 1

您缺少行尾的 ,，这使得添加到队列中的项目成为 tuple。

正常的方法是使用append方法

    if front.left:
        queue.append([front.left, path + "->" + str(front.left.val)])
    if front.right:
        queue.append([front.right, path + "->" + str(front.right.val)])

对于奖励积分，也使用 str.format

    if front.left:
        queue.append([front.left, "{}->{}".format(path, front.left.val)])
    if front.right:
        queue.append([front.right, "{}->{}".format(path, front.right.val)])

并删除附加

中的重复代码

    for node in (front.left, front.right):
        if node:
            queue.append([node, "{}->{}".format(path, node.val)])

Python deque 和 popleft（集合模块的一部分）

Python deque and popleft (part of collections module)

python

collections

binary-tree

breadth-first-search

deque