GESP 六级 · GESP 202403 C++ 六级 第 8 题

阅读以下广度优先搜索的代码：

void bfs(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        TreeNode* current = q.front();
        q.pop();
        cout << current->val << " ";
        if (current->left) {
            q.push(current->left);
        }
        if (current->right) {
            q.push(current->right);
        }
    }
}

使用以上算法遍历以下这棵树，可能的输出是（ ）。

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

排列组合问题：先判断是否考虑顺序（排列P vs 组合C），再确定是否允许重复。乘法原理分步，加法原理分类。

区分排列（考虑顺序，$P(n,m)$）和组合（不考虑顺序，$C(n,m)$）。注意特殊元素优先处理、正难则反等计数技巧。

【考点】广度优先遍历｜队列操作｜二叉树层级顺序

看到队列代码立刻锁定「先入先出」和「左子优先」两个铁律。节点被压入队列的顺序，就是它们最终输出的顺序——这是 BFS 的本质。

模拟队列变化：初始推入 1；弹出 1 后压 2、3；弹出 2 后压 8、9；弹出 3 后压 6；弹出 8 后压无；弹出 9 后压 4、5；弹出 6 后压 7；弹出 4 后压无；弹出 5 后压 10、11；弹出 7 后压无；最后弹出 10、11。输出序列：1 2 3 8 9 6 4 5 7 10 11，与 C 完全匹配。

逐一排除错误选项的底层逻辑：

• A 把 3 放到 8、9 之后：队列里 3 早在 8、9 之前就被压入，不可能晚出。
• B 把 8、9 放到 4、5 之后：8、9 是 2 的子节点，4、5 是 9 的子节点，BFS 必须先处理完 2 这一层的所有节点，才能轮到 9 的子节点。
• D 把 4、5 放到 6 之后：6 是 3 的唯一子节点，4、5 是 9 的子节点，队列顺序是 8