/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return int整型vector<vector<>>
     */
    vector<vector<int> > levelOrder(TreeNode* root) {
        vector<vector<int>> result;
        
        // 如果根节点为空，直接返回空结果
        if (root == nullptr) {
            return result;
        }
        
        // 使用队列进行层序遍历
        queue<TreeNode*> q;
        q.push(root);
        
        while (!q.empty()) {
            // 获取当前层的节点数量
            int levelSize = q.size();
            // 创建当前层的子数组
            vector<int> currentLevel;
            
            // 遍历当前层的所有节点
            for (int i = 0; i < levelSize; i++) {
                TreeNode* node = q.front();
                q.pop();
                
                // 将节点值加入当前层
                currentLevel.push_back(node->val);
                
                // 将子节点加入队列
                if (node->left != nullptr) {
                    q.push(node->left);
                }
                if (node->right != nullptr) {
                    q.push(node->right);
                }
            }
            
            // 将当前层加入结果
            result.push_back(currentLevel);
        }
        
        return result;
    }
};



1. 问题本质分析
层序遍历的核心需求：按照"先遇到的节点先处理"的顺序遍历二叉树。
这正好符合先进先出（FIFO） 的特性：
先被访问的节点，它的子节点也应该先被访问
后加入的节点要等前面的节点处理完才能处理

第二步：寻找匹配的数据结构
栈（LIFO）：后进先出，适合深度优先搜索
队列（FIFO）：先进先出，正好匹配我们的需求

3. 与其他数据结构的对比

4. 队列的天然优势
队列完美解决了两个关键问题：
顺序保证：确保节点按发现的先后顺序处理
层次分离：通过记录每层开始时的队列大小，自然区分不同层次

6. 更广泛的模式识别
这种"用队列实现BFS"的模式在很多场景中都适用：
树的层序遍历
图的广度优先搜索
迷宫最短路径问题
社交网络中的朋友推荐
一旦你识别出问题是"按扩散顺序遍历"或"寻找最短路径"，队列就是首选工具。
总结
选择队列不是偶然的，而是因为：
问题特性：层序遍历本质是广度优先，需要FIFO顺序
数据结构匹配：队列的FIFO特性正好满足需求
实现简洁性：队列操作简单直观，代码易于理解和维护
效率考虑：队列操作的时间复杂度都是O(1)，整体算法O(n)