N 叉树的层序遍历详解与代码实现

N 叉树的层序遍历详解与代码实现

引用

CSDN

1.

https://m.blog.csdn.net/yq20210216/article/details/145608598

N叉树的层序遍历是算法和数据结构中的一个重要概念，广泛应用于计算机科学和软件工程领域。本文将详细介绍如何通过广度优先搜索（BFS）实现N叉树的层序遍历，并提供完整的代码示例。

1.题目

给定一个 N 叉树，返回其节点值的层序遍历。（即从左到右，逐层遍历）。

树的序列化输入是用层序遍历，每组子节点都由 null 值分隔（参见示例）。

示例 1：

**输入：**root = [1,null,3,2,4,null,5,6]
**输出：**[[1],[3,2,4],[5,6]]

示例 2：

**输入：**root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
**输出：**[[1],[2,3,4,5],[6,7,8,9,10],[11,12,13],[14]]

2.思路

层序遍历，BFS

3.代码

/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;
    Node() {}
    Node(int _val) {
        val = _val;
    }
    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/
class Solution {
public:
    // 该函数用于对 N 叉树进行层序遍历，返回每一层节点值组成的二维向量
    vector<vector<int>> levelOrder(Node* root) {
        // 用于存储最终的层序遍历结果，是一个二维向量，每一行代表树的一层
        vector<vector<int>> ret;
        // 如果根节点为空，说明树为空，直接返回空的结果向量
        if(!root) return ret;
        // 定义一个队列，用于辅助进行层序遍历，队列中存储的是节点指针
        queue<Node*> q;
        // 将根节点加入队列，作为层序遍历的起始点
        q.push(root);
        // 当队列不为空时，继续进行层序遍历
        while(q.size()){
            // 获取当前队列的大小，这个大小代表了当前层的节点数量
            int size = q.size();
            // 用于存储当前层的节点值
            vector<int> tmp;
            // 遍历当前层的所有节点
            for(int i = 0; i < size; ++i){
                // 获取队列头部的节点
                Node* p = q.front();
                // 将队列头部的节点从队列中移除
                q.pop();
                // 将当前节点的值加入到存储当前层节点值的向量中
                tmp.push_back(p->val);
                // 遍历当前节点的所有子节点
                for(int j = 0; j < p->children.size(); ++j)
                    // 将当前节点的子节点加入队列，以便后续处理
                    q.push(p->children[j]);
            }
            // 将存储当前层节点值的向量加入到最终结果向量中
            ret.push_back(tmp);
        }
        // 返回最终的层序遍历结果
        return ret;
    }
};

本文原文来自CSDN