GESP 六级 · GESP 202509 C++ 六级 第 12 题

令 $ n $ 是树的节点数目，下列代码实现了树的广度优先遍历，其时间复杂度是（ ）。

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

分析时间复杂度时关注循环层数和每层迭代次数，递归算法则分析递归树。注意最坏/最好/平均情况的区别。

分析复杂度时注意外层循环和内层循环的关联。例如内外两层都到n的循环不一定是O(n²)，要看内层是否每次都在缩小。

【考点】广度优先遍历｜时间复杂度分析｜队列操作｜GESP 六级算法模块明确要求掌握 BFS/DFS 遍历及其复杂度分析。命题人卡住的是学生把遍历过程误当成递归深度或图论复杂度的直觉偏差。解题关键在队列不重复入队——树的边数恒为 $n-1$，每个节点最多被访问两次（左右子节点），但总入队次数恒为 $n$（根入队 + 每次入队一个子节点）。每节点进队出队各一次，总操作次数与节点数成正比，故时间复杂度为 $O(n)$。选项陷阱：B 项 $O(\log n)$ 源于学生误把遍历当成"搜索"——极易把深度 $O(\log n)$ 的平衡树当成所有树的通用规律；C 项 $O(n^2)$ 源于认为每次处理一个节点都要扫描整棵树；D 项 $O(2^n)$ 源于把树的分支当成二叉树所有子节点都要遍历 $2^n$ 种组合。反命题视角：若把遍历改成 DFS 或用邻接表存图，答案不变；若遍历的是 $n$ 个点的完全图，边数 $O(n^2)$ 则复杂度变为 $O(n^2)$。刷到类似题时先问自己：遍历的是树还是图，边数是否随 $n$ 二次增长？