队列+宽搜(BFS)-429.N叉树的层序遍历-力扣(LeetCode)

目录

一、题目解析

1、层序遍历：一层一层，从左往右遍历

2、最后需要返回一个二维数组

二、算法原理

解法：BFS

1、先创建队列用于储存入队节点，二维数组vv用于存储最终结果

2、先判断root根节点是否为空，不为空则入队，为空则返回vv(vv未初始化，所以也为空)

3、如何保证完成层序遍历？在进行4操作之前需统计队列中的元素个数，此时的个数等于上次循环入队孩子节点的个数，也就是该层元素个数

4、由于队列先进先出的性质，将最开始入队的元素pop掉，循环操作，保存节点的值，和入(push)孩子节点(孩子节点在children数组中)，将保存的值尾插(push_back)到vv中

5、当最后队列元素为空，即得到最终结果

三、代码示例

看到最后，如果对您有所帮助，还请点赞、收藏和关注一键三连，在未来还会继续带来优秀的内容，感谢观看，我们下期再见！

一、题目解析

1、层序遍历：一层一层，从左往右遍历

2、最后需要返回一个二维数组

二、算法原理

解法：BFS

1、先创建队列用于储存入队节点，二维数组vv用于存储最终结果

2、先判断root根节点是否为空，不为空则入队，为空则返回vv(vv未初始化，所以也为空)

3、如何保证完成层序遍历？在进行4操作之前需统计队列中的元素个数，此时的个数等于上次循环入队孩子节点的个数，也就是该层元素个数

4、由于队列先进先出的性质，将最开始入队的元素pop掉，循环操作，保存节点的值，和入(push)孩子节点(孩子节点在children数组中)，将保存的值尾插(push_back)到vv中

5、当最后队列元素为空，即得到最终结果

对队列陌生的读者可以自行查看链接

链接：queue - C++ Reference

三、代码示例

class Solution {
public:
    vector<vector<int>> levelOrder(Node* root)
    {
        queue<Node*> qn;
        vector<vector<int>> vv;
        if(root) qn.push(root);
        else return vv;
        while(qn.size())
        {
            int num = qn.size();
            vector<int> v;
            Node* tmp;
            //出队列
            while(num--)
            {
                tmp = qn.front();
                qn.pop();
                v.push_back(tmp->val);
                //入孩子
                for(int i = 0;i<tmp->children.size();i++)
                {
                    qn.push(tmp->children[i]);
                }
            }
            vv.push_back(v);
        }
        return vv;
    }
};

看到最后，如果对您有所帮助，还请点赞、收藏和关注一键三连，在未来还会继续带来优秀的内容，感谢观看，我们下期再见！