层次遍历二叉树cpp

层次遍历也叫做广度优先搜索（Breadth-First Search, BFS），它是从根节点开始，按照从上到下、从左到右的顺序逐层访问二叉树的节点。在C++中，我们可以使用队列（Queue）来辅助完成这个过程。以下是层次遍历二叉树的基本步骤：

1. 定义一个队列，并将根节点入队。
2. 当队列不为空时，循环执行以下操作：
a. 弹出队首元素，打印该节点值。
b. 若该节点有左右子节点，将它们依次入队。
3. 循环直到队列为空。

#include <iostream>
#include <queue>

void levelOrderTraversal(TreeNode* root) {
    if (root == nullptr) return;

    // 创建一个队列，用于存储待处理的节点
    std::queue<TreeNode*> queue;
    queue.push(root);

    while (!queue.empty()) {
        // 弹出并处理当前层的所有节点
        int size = queue.size();
        for (int i = 0; i < size; ++i) {
            TreeNode* node = queue.front();
            std::cout << node->val << " "; // 打印节点值
            // 将当前节点的子节点入队
            if (node->left != nullptr) queue.push(node->left);
            if (node->right != nullptr) queue.push(node->right);
            // 每处理完一层，移动指针到下一个节点
            queue.pop();
        }
        std::cout << '\n'; // 到达新层时换行
    }
}

// 示例中的TreeNode结构体省略