Python层序遍历(Level Order Traversal)能否优化至O(n)时间复杂度？

当然可以实现，使用Python标准库collections模块自带的deque（双端队列）即可完美解决这个问题：deque的左端弹出popleft()、右端追加append()操作的时间复杂度均为O(1)，替代普通列表作为队列使用后，层序遍历整体时间复杂度就能达到O(n)。

优化后代码实现 #

from collections import deque

def levelorder(root):
    if root is None:
        return
    queue = deque()
    queue.append(root)
    while queue:
        node = queue.popleft()
        # 若需要打印节点本身可改为 print(node)
        print(node.val)
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)

原理说明 #

普通Python列表是基于连续内存实现的线性表，执行pop(0)时需要将后续所有元素向前移动一位，因此时间复杂度为O(k)，k是当前列表长度，对应树的层宽，最坏情况完美二叉树底层有n/2个节点，整体复杂度就会达到O(n²)。
而deque基于双向链表实现，修改首尾节点指针即可完成弹出和追加操作，两种操作都是常数时间，所有节点只会入队、出队各一次，整体复杂度稳定为O(n)。

无额外导入的O(n)实现方案 #

如果不想引入标准库导入，也可以用两层列表按层遍历的方案，同样能达到O(n)的时间复杂度：

def levelorder(root):
    if root is None:
        return
    current_level = [root]
    while current_level:
        next_level = []
        for node in current_level:
            print(node.val)
            if node.left:
                next_level.append(node.left)
            if node.right:
                next_level.append(node.right)
        current_level = next_level

该方案不需要弹出队首元素，仅做顺序遍历和尾部追加，同样避免了O(k)的移动开销。

内容的提问来源于stack exchange，提问作者Mayank Parashar