二叉树BFS遍历实现输出与预期不符，该代码是否正确？

你的BFS实现错误核心是违背了队列先进先出（FIFO）的特性，问题出在两处逻辑：

• 循环内多余的queue.reverse()反转队列操作
• 用列表默认的pop()（弹出末尾元素，对应栈的后进先出逻辑）代替队列需要的头部弹出操作

错误逻辑拆解 #

我们以你给出的测试树为例，看你代码中队列的变化过程：

1. 初始队列：[10]，第一次循环反转后为[10]，pop得到10，插入左右孩子6、15，队列变为[6,15]
2. 第二次循环反转队列得到[15,6]，pop得到6，插入左右孩子3、8，队列变为[15,3,8]
3. 第三次循环反转队列得到[8,3,15]，pop得到15，插入右孩子20，队列变为[8,3,20]
4. 第四次循环反转队列得到[20,3,8]，pop得到8，没有子节点，队列变为[20,3]
   到这一步你就已经先把8加入结果集，跳过了本该先处理的3，最终输出顺序自然不符合预期。

修正方案 #

最小改动版本 #

直接删除反转操作，改用pop(0)弹出列表头部元素，符合队列特性：

def BFS(self):
    data = []
    queue = []
    node = self.root
    queue.append(node)
    while len(queue) != 0:
        node = queue.pop(0)
        data.append(node.val)
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)
    return data

性能优化版本 #

列表的pop(0)时间复杂度为O(n)，更推荐用Python标准库的deque实现队列，popleft()操作时间复杂度为O(1)：
首先导入依赖：

from collections import deque

修改BFS方法：

def BFS(self):
    data = []
    queue = deque()
    node = self.root
    queue.append(node)
    while queue:
        node = queue.popleft()
        data.append(node.val)
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)
    return data

修正后运行代码，输出结果为你预期的[10, 6, 15, 3, 8, 20]。

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