C++如何实现二叉树的广度优先搜索（BFS层序遍历）-C++-PHP中文网

std::queue实现bfs层序遍历的核心是利用fifo特性，每层前用q.size()冻结节点数，循环pop并压入非空子节点，避免混层；须判空树、存指针、不入nullptr。

c++如何实现二叉树的广度优先搜索（bfs层序遍历）

用 `std::queue` 实现 BFS 层序遍历最直接

核心就是借助队列的 FIFO 特性，逐层把节点压入、弹出、访问子节点。C++ 标准库的 std::queue 足够可靠，无需手写队列结构。

关键点在于：每次处理一层前，先记录当前队列长度（即本层节点数），然后循环 pop 这么多次，对每个弹出节点把它的 left 和 right 指针非空时压入队列。这样能天然隔离层级。

常见错误是直接在循环中边 pop 边 push，却不固定本层大小，导致下层节点混入本轮遍历 —— 结果变成“看似 BFS，实为乱序”。

必须在每层开始前用 int levelSize = q.size() 冻结当前层宽度
不要用 while (!q.empty()) 套一层就完事，那样无法分层输出或处理
空树要特判：if (!root) return;，否则对空指针取 ->left 会崩溃

如何按层返回二维 vector（如 LeetCode 102）

典型需求是返回 vector<vector>></vector>，每内层 vector 对应一层节点值。这要求你在每次处理完一层后，把该层所有值塞进一个临时 vector<int></int>，再 push_back 到结果中。

注意别在内层循环里反复调用 result.push_back({val}) —— 那样每节点建一个 vector，效率低且结构错乱。

示例片段：

C++14

C++14 对 C++11 的修正与增强版本，适合旧系统维护和较老工具链兼容。

下载

vector<vector>> levelOrder(TreeNode* root) {
    vector<vector>> res;
    if (!root) return res;
    queue<treenode> q;
    q.push(root);
    while (!q.empty()) {
        int n = q.size();
        vector<int> level;
        for (int i = 0; i val);
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }
        res.push_back(level); // ← 整层 push，不是单个节点
    }
    return res;
}
</int></treenode></vector></vector>