⭐北邮复试刷题429. N 叉树的层序遍历(按层入队出队BFS)

2024-02-18 09:44

本文主要是介绍⭐北邮复试刷题429. N 叉树的层序遍历(按层入队出队BFS),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

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,只不过每次从队列拿元素的时候一次将一层的节点全部拿出,再将这些节点下层的children都同时入队即可。这样会造成最后多一次入队出队,所以最后加上一次判空操作即可;

代码:

/*
// Definition for a Node.
class Node {public int val;public List<Node> children;public Node() {}public Node(int _val) {val = _val;}public Node(int _val, List<Node> _children) {val = _val;children = _children;}
};
*/class Solution {public List<List<Integer>> levelOrder(Node root) {Queue<Node> queue = new LinkedList<>();List<List<Integer>> res = new ArrayList<>();if(root == null){return res;}queue.offer(root);List<Integer> list = new ArrayList<>();list.add(root.val);res.add(list);while(!queue.isEmpty()){// 队列想边拿边加时,则利用长度字段;想只拿不加可以用队列判空,最后队列再加;List<List<Node>> tmpList = new ArrayList<>();while(!queue.isEmpty()){// 出队// 将同层的节点一次拿出Node tmpQueueOne = queue.poll();if(tmpQueueOne.children != null)tmpList.add(tmpQueueOne.children);}if(tmpList == null || tmpList.size() == 0)continue;int tmpLen = tmpList.size();List<Integer> tmpResOfOne = new ArrayList<>();for(int i=0;i<tmpLen;i++){if(tmpList.get(i) != null){for(int j=0;j<tmpList.get(i).size();j++){tmpResOfOne.add(tmpList.get(i).get(j).val);// 入队// 将本层下层的孩子全部同时入队queue.offer(tmpList.get(i).get(j));}}}if(tmpResOfOne == null || tmpResOfOne.size() == 0)continue;res.add(tmpResOfOne);}return res;}
}

在这里插入图片描述

这篇关于⭐北邮复试刷题429. N 叉树的层序遍历(按层入队出队BFS)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/720774

相关文章

hdu1254(嵌套bfs,两次bfs)

/*第一次做这种题感觉很有压力,思路还是有点混乱,总是wa,改了好多次才ac的思路:把箱子的移动当做第一层bfs,队列节点要用到当前箱子坐标(x,y),走的次数step,当前人的weizhi(man_x,man_y),要判断人能否将箱子推到某点时要嵌套第二层bfs(人的移动);代码如下:

poj 2195 bfs+有流量限制的最小费用流

题意: 给一张n * m(100 * 100)的图,图中” . " 代表空地, “ M ” 代表人, “ H ” 代表家。 现在,要你安排每个人从他所在的地方移动到家里,每移动一格的消耗是1,求最小的消耗。 人可以移动到家的那一格但是不进去。 解析: 先用bfs搞出每个M与每个H的距离。 然后就是网络流的建图过程了,先抽象出源点s和汇点t。 令源点与每个人相连,容量为1,费用为

POJ 3057 最大二分匹配+bfs + 二分

SampleInput35 5XXDXXX...XD...XX...DXXXXX5 12XXXXXXXXXXXXX..........DX.XXXXXXXXXXX..........XXXXXXXXXXXXX5 5XDXXXX.X.DXX.XXD.X.XXXXDXSampleOutput321impossible

leetcode105 从前序与中序遍历序列构造二叉树

根据一棵树的前序遍历与中序遍历构造二叉树。 注意: 你可以假设树中没有重复的元素。 例如,给出 前序遍历 preorder = [3,9,20,15,7]中序遍历 inorder = [9,3,15,20,7] 返回如下的二叉树: 3/ \9 20/ \15 7   class Solution {public TreeNode buildTree(int[] pr

深度优先(DFS)和广度优先(BFS)——算法

深度优先 深度优先搜索算法(英语:Depth-First-Search,DFS)是一种用于遍历或搜索树或图的算法。 沿着树的深度遍历树的节点,尽可能深的搜索树的分支,当节点v的所在边都己被探寻过,搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点,则选择其中一个作为源节点并重复以上过程,整个进程反复进行直到所有节点都被访

【每日刷题】Day113

【每日刷题】Day113 🥕个人主页:开敲🍉 🔥所属专栏:每日刷题🍍 🌼文章目录🌼 1. 91. 解码方法 - 力扣(LeetCode) 2. LCR 098. 不同路径 - 力扣(LeetCode) 3. 63. 不同路径 II - 力扣(LeetCode) 1. 91. 解码方法 - 力扣(LeetCode) //思路:动态规划。 cl

PHP实现二叉树遍历(非递归方式,栈模拟实现)

二叉树定义是这样的:一棵非空的二叉树由根结点及左、右子树这三个基本部分组成,根据节点的访问位置不同有三种遍历方式: ① NLR:前序遍历(PreorderTraversal亦称(先序遍历)) ——访问结点的操作发生在遍历其左右子树之前。 ② LNR:中序遍历(InorderTraversal) ——访问结点的操作发生在遍历其左右子树之中(间)。 ③ LRN:后序遍历(PostorderT

react笔记 8-17 属性绑定 class绑定 引入图片 循环遍历

1、绑定属性 constructor(){super()this.state={name:"张三",title:'我是一个title'}}render() {return (<div><div>aaaaaaa{this.state.name}<div title={this.state.title}>我是一个title</div></div></div>)} 绑定属性直接使用花括号{}   注

hot100刷题第1-9题,三个专题哈希,双指针,滑动窗口

求满足条件的子数组,一般是前缀和、滑动窗口,经常结合哈希表; 区间操作元素,一般是前缀和、差分数组 数组有序,更大概率会用到二分搜索 目前已经掌握一些基本套路,重零刷起leetcode hot 100, 套路题按套路来,非套路题适当参考gpt解法。 一、梦开始的地方, 两数之和 class Solution:#注意要返回的是数组下标def twoSum(self, nums: Lis

代码随想录刷题day25丨491.递增子序列 ,46.全排列 ,47.全排列 II

代码随想录刷题day25丨491.递增子序列 ,46.全排列 ,47.全排列 II 1.题目 1.1递增子序列 题目链接:491. 非递减子序列 - 力扣(LeetCode) 视频讲解:回溯算法精讲,树层去重与树枝去重 | LeetCode:491.递增子序列_哔哩哔哩_bilibili 文档讲解:https://programmercarl.com/0491.%E9%80%92%E