GESP 六级 · GESP 202412 C++ 六级 第 13 题

使用上题中的宽度优先搜索算法遍历以下这棵树，可能的输出是（ ）。

    1
   / \
  2   3
 / \   \
8   9   6
   / \   \
  4   5   7

根据二叉树的遍历特性，先/前序遍历确定根节点，中序遍历确定左右子树范围，从而重构整棵树，再输出后序遍历结果。

易混淆三种遍历的顺序。先序：根左右；中序：左根右；后序：左右根。注意遍历结果中相邻节点的关系。

【考点】BFS｜树｜遍历

解题思维 BFS 的本质是按层访问，必须用队列实现：根入队→弹出根、子节点依次入队→弹出下一层所有节点。题目这棵树层次分明，从根开始逐层展开，队列弹出的顺序天然就是层序遍历结果：1→2,3→8,9,6→4,5,7，拼起来就是 1 2 3 8 9 6 4 5 7。

陷阱拆解 A 把 8,9 提前到 3 之前，违反"同层先左后右"，队列里 3 还在就轮不到 8；B 里 4,5 在 6 之前，说明已经跳层访问，这是 DFS 的典型特征；D 从叶子 8 开头，完全违背 BFS 必须从根开始的铁律。这些都是利用学生"只背结论、不看过程"的惯性思维设计的坑。

反命题思维 命题人想卡住的是"队列顺序意识"。如果改成右子树优先入队，层序结果会变：1 2 3 8 9 6 4 5 7 变成 1 2 3 9 8 6 5 4 7，答案就不同了。刷到类似题先问自己：队列里元素的进出顺序对吗？