【leetcode】429. N 叉树的层序遍历

本文主要是介绍【leetcode】429. N 叉树的层序遍历，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

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

---

代码

bfs

class Solution {  public List<List<Integer>> levelOrder(Node root) {  Queue<Node> queue = new LinkedList<>();  ArrayList<List<Integer>> lists = new ArrayList<>();  if (root == null) return lists;  lists.add(new ArrayList<Integer>(){{add(root.val);}});  for (Node child : root.children) {  queue.add(child);  }  while (!queue.isEmpty()) {  int len = queue.size();  ArrayList<Integer> temp = new ArrayList<>();  for (int i = 0; i < len; i++) {  Node poll = queue.poll();  temp.add(poll.val);  for (Node child : poll.children) {  queue.add(child);  }  }  lists.add(temp);  }  return lists;  }  
}

dfs

class Solution {  List<List<Integer>> ans = new ArrayList<>();  public List<List<Integer>> levelOrder(Node root) {  dfs(root, 1);  return ans;  }  private void dfs(Node node, int deep) {  if (node == null) return;  if (ans.size() < deep) {  ans.add(new ArrayList<>());  }  ans.get(deep - 1).add(node.val);  for (Node child : node.children) {  dfs(child, deep + 1);  }  }  
}

---

题解

bfs

借助队列来完成bfs操作
先按顺序遍历一层的所有节点, 并把他们的所有子节点按顺序放入队列中
如此一轮遍历后, 队列就被存满了下一层的的节点存满了
如法炮制的多次循环把直到队列为空就得到答案了

dfs

用函数传递的参数表示当前栈的深度(从1开始)
应为深度也可以对应List下标, 所以很容易对对当前栈代表节点的值进行存储

---

具体代码参上

好的!本次分享到这就结束了
如果对铁汁你有帮助的话，记得点赞👍+收藏⭐️+关注➕
我在这先行拜谢了：）

这篇关于【leetcode】429. N 叉树的层序遍历的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---