二叉树及n叉树的层序遍历，看这一篇就够

关于Leetcode上二叉树及n叉树的层序遍历

层序遍历二叉树，顾名思义，就是从左到右一层一层的去遍历二叉树。

通常需要借用一个辅助数据结构即队列来实现，队列先进先出，符合一层一层遍历的逻辑，而用栈先进后出适合模拟深度优先遍历也就是递归的逻辑。而这种层序遍历方式就是图论中的广度优先遍历，只不过我们应用在二叉树上。
下面上题目:

题面及样例输入输出：

题目来源：leetcode（力扣）

题目链接：https://leetcode-cn.com/problems/binary-tree-level-order-traversal/

源代码及注释：

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        queue<TreeNode*>que; //定义队列
        vector<vector<int>>res;
        if(root != nullptr)//空指针直接返回
        que.push(root);
        while(!que.empty())//队列为空是终止条件
        {
            vector<int>path;
            int size = que.size();//取队列中的元素个数
            for(int i = 0; i < size; i++)//这里只能采用size，因为循环中que.size（）是在不断改变的
            {
                TreeNode* cur = que.front();//取队首元素
                que.pop();//d出该元素
                path.push_back(cur -> val);//将遍历的元素放入path中
                if(cur -> left)//左孩子不为空
                que.push(cur -> left);//左孩子入队列
                if(cur -> right)//右孩子不为空
                que.push(cur -> right);//右孩子入队列
            }
            res.push_back(path);//path放入result中
        }
        return res;//返回最终结果res

    }

};

上面的代码也就是二叉树层序遍历的模板，以后遇到有关层序遍历的题目，只需要将这个模板修改活用即可。

二叉树如此，那有同学会问n叉树呢？

别急别急，其实本质上与二叉树相同，如以下题目

题面及样例输入输出：

题目来源：leetcode（力扣）

题目链接：https://leetcode-cn.com/problems/n-ary-tree-level-order-traversal/

源代码及注释：

class Solution {
public:
    vector<vector<int>> levelOrder(Node* root) {
        queue<Node*>que;
        vector<vector<int>>res;
        if(root == nullptr)
        return res;
        que.push(root);
        while(!que.empty())
        {
           
            int size = que.size();
            vector<int>path;
            for(int i = 0; i < size; i++)
            {
                Node* cur = que.front();
                que.pop();
                path.push_back(cur -> val);
                if(!(cur -> children).empty())//如果指针cur的孩子指针不为空
                {
                    for(int i = 0; i < cur->children.size(); i++)//循环
                    que.push(cur->children[i]);//将指针cur的所有孩子入队列
                }
            }
            res.push_back(path);
        }
        return res;
    }
};

可以看出，n叉树的层序遍历相较于二叉树的层序遍历，只是多添加了一个循环，其根本目的是不变的：都是为了将所有孩子加入队列。

相信通过这篇文章，大家对二叉树及n叉树的层序遍历都有了一定程度上的了解。

大家可以通过leetcode上的以下题目来测试自己对层序遍历的掌握程度：

• 102.二叉树的层序遍历
• 107.二叉树的层次遍历II
• 199.二叉树的右视图
• 637.二叉树的层平均值
• 429.N叉树的层序遍历
• 515.在每个树行中找最大值
• 116.填充每个节点的下一个右侧节点指针
• 117.填充每个节点的下一个右侧节点指针II
• 104.二叉树的最大深度
• 111.二叉树的最小深度均值
• 429.N叉树的层序遍历
• 515.在每个树行中找最大值
• 116.填充每个节点的下一个右侧节点指针
• 117.填充每个节点的下一个右侧节点指针II
• 104.二叉树的最大深度
• 111.二叉树的最小深度

最后，希望这篇文章对大家有所帮助！