LeetCode-429 N叉树的层次遍历

简介: LeetCode-429 N叉树的层次遍历

来源:力扣(LeetCode)

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

著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

题目描述

给定一个 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]]

 

提示:

树的高度不会超过 1000

树的节点总数在 [0, 10^4] 之间

解题思路

利用一个队列记录当前层的结点,一个队列记录下一层的结点,遍历当前层就将下一层作为当前层进行遍历。注意判断结点为空的条件

代码展示

 

/*
// 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:
    vector<vector<int>> levelOrder(Node* root) {
        vector<vector<int>> vviRet;
        queue<Node*> visiting;
        if(!root) return vviRet;
        visiting.push(root);
        while(!visiting.empty())
        {
            queue<Node*> ch = visiting;
            visiting = queue<Node*>();
            vector<int> viRet;
            while(!ch.empty())
            {
                auto p = ch.front();
                ch.pop();
                viRet.push_back(p->val);
                for(auto iter: p->children)
                    if(iter)
                        visiting.push(iter);
            }
            vviRet.push_back(viRet);
        }
        return vviRet;
    }
};

运行结果

 

相关文章
|
3月前
|
Python
【Leetcode刷题Python】剑指 Offer 26. 树的子结构
这篇文章提供了解决LeetCode上"剑指Offer 26. 树的子结构"问题的Python代码实现和解析,判断一棵树B是否是另一棵树A的子结构。
50 4
|
3月前
|
Python
【Leetcode刷题Python】538. 把二叉搜索树转换为累加树
LeetCode上538号问题"把二叉搜索树转换为累加树"的Python实现,使用反向中序遍历并记录节点值之和来更新每个节点的新值。
21 3
|
6月前
|
算法 C语言 容器
从C语言到C++_25(树的十道OJ题)力扣:606+102+107+236+426+105+106+144+94+145(下)
从C语言到C++_25(树的十道OJ题)力扣:606+102+107+236+426+105+106+144+94+145
64 7
|
6月前
|
C语言
从C语言到C++_25(树的十道OJ题)力扣:606+102+107+236+426+105+106+144+94+145(中)
从C语言到C++_25(树的十道OJ题)力扣:606+102+107+236+426+105+106+144+94+145
54 1
|
6月前
|
算法 C语言 C++
从C语言到C++_25(树的十道OJ题)力扣:606+102+107+236+426+105+106+144+94+145(上)
从C语言到C++_25(树的十道OJ题)力扣:606+102+107+236+426+105+106+144+94+145
40 1
|
6月前
LeetCode———100——相同的树
LeetCode———100——相同的树
|
6月前
力扣337.打家劫舍3(树形dp)
力扣337.打家劫舍3(树形dp)
|
5月前
|
SQL 算法 数据可视化
LeetCode题目99:图解中叙遍历、Morris遍历实现恢复二叉树搜索树【python】
LeetCode题目99:图解中叙遍历、Morris遍历实现恢复二叉树搜索树【python】
|
5月前
|
存储 SQL 算法
LeetCode题目100:递归、迭代、dfs使用栈多种算法图解相同的树
LeetCode题目100:递归、迭代、dfs使用栈多种算法图解相同的树
|
5月前
|
存储 算法 数据可视化
python多种算法对比图解实现 验证二叉树搜索树【力扣98】
python多种算法对比图解实现 验证二叉树搜索树【力扣98】