leetcode——第429题——N叉树的层序遍历-白红宇

leetcode——第429题——N叉树的层序遍历

阅读量：540 次

发布时间：2019-03-09

本文共 1001 字，大约阅读时间需要 3 分钟。

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

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

解决方案：实现对任意 N 叉树的层序遍历，按照给定格式返回各层节点的值。具体方法如下：

初始化队列：使用一个队列来存储当前层的节点。

处理根节点：如果根节点不为空，将其加入队列。

循环处理：while 队列不为空，逐层处理节点。

记录当前层节点数量：获取队列中节点的数量，作为当前层的节点总数。

创建结果列表：初始化当前层的结果列表。

遍历队列：逐个处理队列中的节点，提取其值。

处理子节点：递归地将每个节点的子节点加入下一层队列。

返回结果：将每层的结果按顺序存储，并最终返回完整结果。

测试示例：假设输入为 1,null,2,null,3，则输出应为：

完整代码如下：

#include 
   
    #include 
    
     using namespace std;vector
     
       levelOrder(Node* root) {    vector
      
        result;    queue
       
         que;        if (root != nullptr) {        que.push(root);    }        while (!que.empty()) {        int size = que.size();        vector
        
          level; for (int i = 0; i < size; i++) { Node* node = que.front(); que.pop(); level.push_back(node->val); for (size_t j = 0; j < node->children.size(); j++) { if (node->children[j] != nullptr) { que.push(node->children[j]); } } } result.push_back(level); } return result;}