C++ 两种方法实现 N 叉树的层序遍历：详细解析与代码分析

本文将深入探讨两种使用 C++ 实现 N 叉树层序遍历的方法，并对两种方法的代码进行逐行分析，帮助你理解不同方法的思路和实现细节。同时，文章还比较了两种方法的优缺点，让你选择最适合你的解决方案。

方法一：使用队列进行层序遍历

class Solution {
public:
    vector<vector<int>> levelOrder(Node* root) {
        vector<vector<int>> leve;
        if(!root){
            return leve;
        }
        queue<Node*> s;
        s.push(root);
        while(!s.empty()){
            leve.push_back(vector<int> ());
            int n=s.size();
            for(int i=0;i<n;i++){
                Node* c=s.front();
                s.pop();
                leve.back().push_back(c->val);
                int len=c->children.size();
                if(len){
                    for(auto& j:c->children)
                    {
                        if(j){
                             s.push(j);
                        }
                    }
                }

            }

        }
        return leve;        
    }
};

代码分析：

初始化: 首先定义一个二维向量 leve 来存储结果，如果根节点为空，直接返回空数组。
创建队列: 使用一个队列 s 来存储待遍历节点，初始时将根节点加入队列。
层序遍历: 使用 while 循环遍历每一层节点。
- leve.push_back(vector<int> ()): 创建一个新的向量来存储当前层的节点值。
- int n=s.size(): 记录当前层节点的个数。
- for(int i=0;i<n;i++): 遍历当前层的所有节点。
  - Node* c=s.front(); s.pop(): 取出队列头部节点，并将其从队列中移除。
  - leve.back().push_back(c->val): 将当前节点的值加入到当前层数组中。
  - int len=c->children.size(): 获取当前节点子节点的数量。
  - if(len) { ... }: 如果当前节点有子节点，将所有子节点加入队列。
返回结果: 返回最终的结果数组 leve。

方法二：使用队列进行层序遍历（简洁版本）

class Solution {
public:
    vector<vector<int>> levelOrder(Node* root) {
        vector<vector<int>>result;
        queue<Node*>que;
        if(root){que.push(root);}
        while(!que.empty()){
            int size=que.size();
            vector<int>vec;
            for(int i=0;i<size;i++){
                Node*node=que.front();
                que.pop();
                vec.push_back(node->val);
                if(node->children.size()){
                    for(int i=0;i<node->children.size();i++){que.push(node->children[i]);}
                }
            }
            result.push_back(vec);
        }
        return result;
    }
};

代码分析：

初始化: 定义一个二维向量 result 来存储结果，如果根节点存在，则将它加入队列 que。
层序遍历: 使用 while 循环遍历每一层节点。
- int size=que.size(): 记录当前层节点的个数。
- vector<int>vec: 创建一个新的向量来存储当前层的节点值。
- for(int i=0;i<size;i++): 遍历当前层的所有节点。
  - Node*node=que.front(); que.pop(): 取出队列头部节点，并将其从队列中移除。
  - vec.push_back(node->val): 将当前节点的值加入到当前层数组中。
  - if(node->children.size()) { ... }: 如果当前节点有子节点，将所有子节点加入队列。
更新结果: 将当前层的节点值数组 vec 加入到结果数组 result 中。
返回结果: 返回最终的结果数组 result。

方法对比

两种方法的基本思想是一样的，都是使用队列来进行层序遍历。

区别在于：

变量命名: 第一种方法使用 s 和 leve 作为队列和结果数组的变量名，而第二种方法使用 que 和 result。
代码风格: 第二种方法的代码更加简洁，使用更直观的变量名，同时将子节点加入队列的循环放在了 if 语句中。
Node 类: 第一种方法中定义了 Node 类，而第二种方法直接使用了题目中给出的 Node 类。

总结: 两种方法的思路是一样的，只是在变量命名和代码风格上稍有不同。选择哪种方法取决于个人喜好和代码风格。

希望这篇文章能帮助你更好地理解 N 叉树的层序遍历，并能够根据你的需求选择最合适的实现方法！