原题
给定一个 N 叉树，返回其节点值的层序遍历。 (即从左到右，逐层遍历)。
例如，给定一个 3叉树 :
返回其层序遍历:
[
[1],
[3,2,4],
[5,6]
]
说明:
1. 树的深度不会超过 1000。
2. 树的节点总数不会超过 5000。
解法
思想
类似leetcode102-二叉树的层次遍历，通过DFS或BFS实现。
代码
迭代（BFS）：
class Solution {
public List<List<Integer>> levelOrder(Node root) {
Queue<Node> queue = new LinkedList<>();
List<List<Integer>> ans = new ArrayList<>();
List<Integer> cur = new ArrayList<>();
if(root == null) return new ArrayList<List<Integer>>();
queue.offer(root);
queue.offer(null);//以null作为每层结束的标志符
while(!queue.isEmpty()){
Node node = queue.poll();
if(node == null){
if(cur.size()!=0) ans.add(cur);
cur = new ArrayList<>();
}else{
cur.add(node.val);
for(Node child:node.children){
if(child!=null) queue.offer(child);
}
//若队首为null说明这一层的节点的子节点已经全部加入队列了，需要加入一个null
if(queue.peek()==null) queue.offer(null);
}
}
return ans;
}
}
递归（DFS）：
class Solution {
List<List<Integer>> ans = new ArrayList<>();
public List<List<Integer>> levelOrder(Node root) {
if(root==null)
return ans;
DFS(root,0);
return ans;
}
public void DFS(Node root,int level){
if(ans.size()==level)
ans.add(new ArrayList<Integer>());
ans.get(level).add(root.val);
for(Node node:root.children){
if(node!=null)
DFS(node,level+1);
}
}
}
原创文章，作者：彭晨涛，如若转载，请注明出处：https://www.codetool.top/article/leetcode429-n%e5%8f%89%e6%a0%91%e7%9a%84%e5%b1%82%e5%ba%8f%e9%81%8d%e5%8e%86/
相关推荐
-
剑指offer51-数组中的逆序对
原题（来源Leetcode） 在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。 示例 1: 输入： [7...
-
剑指offer04-二维数组中的查找
原题（来源Leetcode） 在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个...
-
leetcode4-寻找两个有序数组的中位数
这道题我没想出符合条件的思路 原题 给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。 请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m...
-
leetcode376-摆动序列
原题 如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为摆动序列。第一个差（如果存在的话）可能是正数或负数。少于两个元素的序列也是摆动序列。 例如， [1,7,4,9,...
-
leetcode136-只出现一次的数字
原题 给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。 说明： 你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗...
-
leetcode173-二叉搜索树迭代器
原题 实现一个二叉搜索树迭代器。你将使用二叉搜索树的根节点初始化迭代器。 调用 next() 将返回二叉搜索树中的下一个最小的数。 示例： BSTIterator iterator...
-
蓝桥杯试题-哈夫曼树
原题 Description Huffman树在编码中有着广泛的应用。在这里，我们只关心Huffman树的构造过程。 给出一列数{pi}={p0, p1, …, pn-1}，用这列...
-
leetcode1248-统计「优美子数组」
原题 给你一个整数数组 nums 和一个整数 k。 如果某个 连续 子数组中恰好有 k 个奇数数字，我们就认为这个子数组是「优美子数组」。 请返回这个数组中「优美子数组」的数目。 ...
-
剑指offer50-第一个只出现一次的字符
原题（来源Leetcode） 在字符串 s 中找出第一个只出现一次的字符。如果没有，返回一个单空格。 s 只包含小写字母。 示例: s = "abaccdeff" 返回 "b" s...
-
leetcode295-数据流的中位数
原题 中位数是有序列表中间的数。如果列表长度是偶数，中位数则是中间两个数的平均值。 例如， [2,3,4] 的中位数是 3 [2,3] 的中位数是 (2 + 3) / 2 = 2....