GESP 六级 · GESP 202512 C++ 六级 第 19 题

广度优先遍历二叉树可用栈来实现。

BFS 使用队列，按层次逐层遍历，适合求最短路径（边权为1时）。核心：标记已访问，避免重复入队。

BFS 入队后立即标记已访问，防止重复入队。队列为空时搜索结束。注意区分树的BFS（无需visited标记）和图的BFS。

【考点】二叉树遍历｜栈与队列特性｜BFS/DFS算法原理

GESP六级在算法基础模块卡住大量考生的正是“数据结构与遍历方式”的对应关系。命题人故意把“广度优先”和“栈”配对，就是想测试你是否真正理解数据结构如何决定遍历顺序，而不是死记“BFS=队列，DFS=栈”的结论。

看到BFS先想队列FIFO特性，因为BFS是层序遍历，必须“先进先出”才能按层处理。栈是LIFO，放进去的最后一个节点会最先被弹出，这恰恰是深度优先遍历（DFS）的特征。通用结论：任何“按发现顺序处理”的遍历都必须用队列，任何“按最近处理顺序”的遍历都必须用栈。

陷阱一：把“栈”当成通用容器，忽略LIFO特性，误以为“放进去再拿出来”就是按层处理。陷阱二：混淆BFS和DFS的遍历顺序，认为只要“遍历了所有节点”就满足BFS定义。陷阱三：忽略“队列”在BFS中的核心地位，命题人特意用“栈”制造记忆冲突。

命题人视角：把“栈”换成“链表”（若没加双向指针则做不到FIFO），答案变错；把“广度优先”换成“深度优先”，答案变对。刷到此类题先问自己：题目给的数据结构特性（FIFO/LIFO）和遍历顺序（层序/深度）是否匹配。