【LeetCode】树的BFS(层序遍历)精选6题

目录

1. N 叉树的层序遍历(中等)

2. 二叉树的锯齿形层序遍历(中等)

3. 二叉树的最大宽度(中等)

4. 在每个树行中找最大值(中等)

5. 找树左下角的值(中等)

6. 二叉树的右视图(中等)


1. N 叉树的层序遍历(中等)

先让根结点root入队,队列中:①

第一层遍历:让①出队,让①的孩子③②④入队,队列中:③②④

第二层遍历:让③②④出队,让③的孩子⑤⑥入队(②④没有孩子),队列中:③②④⑤⑥

第三层遍历:让⑤⑥出队,⑤⑥没孩子。

队列为空,层序遍历结束。

代码流程设计:先让根节点入队。然后在每一轮层序遍历中,计算当前队列中节点的个数(即本层节点的个数),记为count,依次让count个节点出队,把本层节点的值放到临时数组中,并让本层节点的孩子(即下一层节点)入队。该轮层序遍历完成后,把临时数组添加到答案中。

class Solution {
public:vector<vector<int>> levelOrder(Node* root) {if (root == nullptr)return {};vector<vector<int>> ans;queue<Node*> q;q.push(root);while (!q.empty()){int count = q.size(); // 本层节点的个数vector<int> tmp; // 记录本层节点的值for (int i = 0; i < count; i++){// 本层节点出队Node* cur = q.front();q.pop();// 把本层节点的值放入临时数组中tmp.push_back(cur->val);// 本层节点的孩子(下一层节点)入队for (auto& child : cur->children){if (child != nullptr){q.push(child);}}}ans.push_back(tmp);}return ans;}
};

2. 二叉树的锯齿形层序遍历(中等)

创建一个变量level表示层数,假设二叉树从第1层开始。level为奇数,正序遍历;level为偶数,逆序遍历。

class Solution {
public:vector<vector<int>> zigzagLevelOrder(TreeNode* root) {if (root == nullptr)return {};vector<vector<int>> ans;queue<TreeNode*> q;q.push(root);int level = 1;while (!q.empty()){int count = q.size(); // 本层节点的个数vector<int> tmp; // 记录本层节点的值for (int i = 0; i < count; i++){// 本层节点出队TreeNode* cur = q.front();q.pop();// 把本层节点的值放入临时数组中tmp.push_back(cur->val);// 本层节点的孩子(下一层节点)入队if (cur->left){q.push(cur->left);}if (cur->right){q.push(cur->right);}}// 如果本层是偶数层,将临时数组反转,再放入答案中if (level % 2 == 0){reverse(tmp.begin(), tmp.end());}ans.push_back(tmp);level++;}return ans;}
};

3. 二叉树的最大宽度(中等)

利用二叉树的顺序存储方式给二叉树的节点编号,假设根结点编号为1,编号为x的节点的两个孩子的编号分别为2x和2x+1。让节点和编号一起入队,每层宽度 = 队尾编号 - 队头编号 + 1。

代码流程设计:先让根节点入队。然后在每一轮层序遍历中,计算本层宽度并更新答案,计算当前队列中节点的个数(即本层节点的个数),记为count,依次让count个节点出队,并让本层节点的孩子(即下一层节点)入队。

如果二叉树的层数非常非常非常多时,任何一种数据类型都存不下编号。因为无符号整型溢出时会自动取模,而且题目数据保证答案将会在32位带符号整数范围内,所以用unsigned int存储编号就可以保证答案正确。

class Solution {
public:int widthOfBinaryTree(TreeNode* root) {unsigned int ans = 0;queue<pair<TreeNode*, unsigned int>> q;q.push({ root,1 });while (!q.empty()){unsigned int width = q.back().second - q.front().second + 1; // 本层宽度ans = max(ans, width);int count = q.size(); // 本层节点的个数for (int i = 0; i < count; i++){// 本层节点出队TreeNode* cur = q.front().first;unsigned int num = q.front().second; // cur的编号q.pop();// 本层节点的孩子(下一层节点)入队if (cur->left){q.push({ cur->left,2 * num });}if (cur->right){q.push({ cur->right,2 * num + 1 });}}}return ans;}
};

4. 在每个树行中找最大值(中等)

层序遍历的过程中找最大值。

class Solution {
public:vector<int> largestValues(TreeNode* root) {if (root == nullptr)return {};vector<int> ans;queue<TreeNode*> q;q.push(root);while (!q.empty()){int count = q.size(); // 本层节点的个数int tmp = INT_MIN;for (int i = 0; i < count; i++){// 本层节点出队TreeNode* cur = q.front();q.pop();// 更新tmptmp = max(tmp, cur->val);// 本层节点的孩子(下一层节点)入队if (cur->left){q.push(cur->left);}if (cur->right){q.push(cur->right);}}ans.push_back(tmp);}return ans;}
};

5. 找树左下角的值(中等)

层序遍历的过程中找最左边的值。

class Solution {
public:int findBottomLeftValue(TreeNode* root) {if (root == nullptr)return {};int ans = 0;queue<TreeNode*> q;q.push(root);while (!q.empty()){int count = q.size(); // 本层节点的个数for (int i = 0; i < count; i++){// 本层节点出队TreeNode* cur = q.front();q.pop();// 如果遍历到本层最左边的节点,更新ansif (i == 0){ans = cur->val;}// 本层节点的孩子(下一层节点)入队if (cur->left){q.push(cur->left);}if (cur->right){q.push(cur->right);}}}return ans;}
};

6. 二叉树的右视图(中等)

层序遍历的过程中找最右边的值。

class Solution {
public:vector<int> rightSideView(TreeNode* root) {if (root == nullptr)return {};vector<int> ans;queue<TreeNode*> q;q.push(root);while (!q.empty()){int count = q.size(); // 本层节点的个数for (int i = 0; i < count; i++){// 本层节点出队TreeNode* cur = q.front();q.pop();// 如果遍历到本层最右边的节点,将值添加到答案if (i == count - 1){ans.push_back(cur->val);}// 本层节点的孩子(下一层节点)入队if (cur->left){q.push(cur->left);}if (cur->right){q.push(cur->right);}}}return ans;}
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/260224.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

票务系统平台架构设计与实现

票务系统是一个复杂的平台&#xff0c;涉及到用户购票、票务管理、支付结算等多方面功能。本文将介绍票务系统平台的架构设计原则、技术选型以及实现过程&#xff0c;帮助读者了解如何构建一个高效、稳定的票务系统。 正文&#xff1a; 1. 系统设计原则 在设计票务系统平台时…

【计算机网络】网络基础

初识网络 一、网络发展二、认识协议三、认识网络协议1. 协议分层2. OSI 七层模型3. TCP/IP五层模型4. OS和网络协议栈 四、网络传输基本流程1. TCP/IP 协议通讯过程2. 以太网通信&#xff08;1&#xff09;以太网通信原理&#xff08;2&#xff09;数据碰撞 3. 数据跨网络传输 …

计算机网络概论和数据通信基础

文章目录 计算机网络概论从物理构成上看&#xff0c;计算机网络包括硬件、软件和协议三大部分计算机网络的功能组成计算机网络的分类网络体系结构分层与体系结构接口、协议和服务数据传送单位OSI模型TCP/IP模型 数据通信基础数字信号调制为模拟信号正交振幅调制QAM 模拟数据编码…

STM32Cubemx TB6612直流电机驱动

一、TB6612FNG TB6612是一个支持双电机的驱动模块&#xff0c;支持PWM调速。PWMA、AIN1、AIN2 为一组控制引脚&#xff0c;PWMA 为 PWM 速度控制引脚&#xff0c;AIN1、AIN2 为方向控制引脚&#xff1b;PWMB、BIN1、BIN2 为一组控制引脚&#xff0c;PWMB 为 PWM 速度控制引脚&…

例40:滚动条的使用

建立一个EXE工程&#xff0c;在窗体上放一个文本框和一个水平滚动条。设置滚动条的最大最小属性分别为&#xff1a;100和1。如图36。 图36 为滚动条的change事件输入代码&#xff1a; Sub Form1_HScroll1_Change(hWndForm As hWnd, hWndControl As hWnd, hNewPos As Long, n…

【高效开发工具系列】PyCharm使用

&#x1f49d;&#x1f49d;&#x1f49d;欢迎来到我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐:kwan 的首页,持续学…

更改WordPress作者存档链接author和用户名插件Change Author Link Structure

WordPress作者存档链接默认情况为/author/Administrator&#xff08;用户名&#xff09;&#xff0c;为了防止用户名泄露&#xff0c;我们可以将其改为/author/1&#xff08;用户ID&#xff09;&#xff0c;具体操作可参考『如何将WordPress作者存档链接中的用户名改为昵称或ID…

【二十四】【C++】多态

多态的基本概念 多态是一种允许使用相同的接口来访问不同的底层形式&#xff08;类型&#xff09;的对象的能力。C中的多态主要通过以下两种方式实现&#xff1a; 编译时多态&#xff08;静态多态&#xff09;&#xff1a;通过函数重载和运算符重载实现。 运行时多态&#x…

wordpress外贸成品网站模板

首页大图slider轮播&#xff0c;橙色风格的wordpress外贸网站模板 https://www.zhanyes.com/waimao/6250.html 蓝色经典风格的wordpress外贸建站模板 https://www.zhanyes.com/waimao/6263.html

C# Winform .net6自绘的圆形进度条

using System; using System.Drawing; using System.Drawing.Drawing2D; using System.Windows.Forms;namespace Net6_GeneralUiWinFrm {public class CircularProgressBar : Control{private int progress 0;private int borderWidth 20; // 增加的边框宽度public int Progr…

通过VSCode开发Python项目

一、插件准备 Python 插件&#xff0c;必须 autoDocstring 生成注释&#xff0c;和Pycharm一样输入三个引号"""会生产注释结构 Todo Tree 高亮显示 TODO/FIXME 二、python相关设置 一&#xff09;设置python环境 按"F1"打开命令面板&#xff08;…

openai公司的chatgpt-3.5参数库内还未增加sora的语料信息

openai公司的chatgpt-3.5参数库内还未增加sora的语料信息&#xff01;我想通过openai公司的chatgpt3.5来了解一下关于sora的技术信息&#xff0c;结果呢&#xff0c;它竟然回答不知道sora是什么。看来&#xff0c;sora的语料库信息还未来得及加入chatgpt3.5的训练模型中。 如图…

vue的十大面试题详情

1 v-show与v-if区别 v-if与v-show可以根据条件的结果,来决定是否显示指定内容&#xff1a; v-if: 条件不满足时, 元素不会存在. v-show: 条件不满足时, 元素不会显示(但仍然存在). <div id"app"><button click"show !show">点我</but…

ELAdmin 隐藏添加编辑按钮

使用场景 做了一个监控模块&#xff0c;数据都是定时生成的&#xff0c;所以不需要手动添加和编辑功能。 顶部不显示 可以使用 true 或者 false 控制现实隐藏 created() {this.crud.optShow {add: false,edit: false,del: true,download: true,reset: true}},如果没有 crea…

ubuntu服务器部署gitlab docker并配置nginx反向代理https访问

拉取镜像 docker pull gitlab/gitlab-ce运行容器 docker run --detach \--publish 9080:80 --publish 9022:22 --publish 9443:443\--namegitlab \--restartalways \--volume /home/docker/gitlab/config:/etc/gitlab \--volume /home/docker/gitlab/logs:/var/log/gitlab \-…

直接查看电脑几核芯几线程的方法

之前查看电脑几核芯几线程时都是点击 此电脑->属性->设备管理器->处理器 但是这样并不能判断是否有多线程 譬如这里&#xff0c;是2核芯2线程还是4核芯&#xff1f; 实际上&#xff0c;打开任务管理器后点击性能查看核芯线程数即可 所以示例这台电脑是4核芯而不是2…

PDF控件Spire.PDF for .NET【安全】演示:如何在 PDF 中添加签名字段

Spire.PDF for .NET 是一款独立 PDF 控件&#xff0c;用于 .NET 程序中创建、编辑和操作 PDF 文档。使用 Spire.PDF 类库&#xff0c;开发人员可以新建一个 PDF 文档或者对现有的 PDF 文档进行处理&#xff0c;且无需安装 Adobe Acrobat。 E-iceblue 功能类库Spire 系列文档处…

html的表单标签(上):form标签和input标签

表单标签 表单是让用户输入信息的重要途径。 用表单标签来完成与服务器的一次交互&#xff0c;比如你登录QQ账号时的场景。 表单分成两个部分&#xff1a; 表单域&#xff1a;包含表单元素的区域&#xff0c;用form标签来表示。表单控件&#xff1a;输入框&#xff0c;提交按…

微信小程序swiper 视频中间大,两边小,轮播滑到中间视频自动播放组件教程

静态效果&#xff1a; 进入下面小程序可以体验效果&#xff0c;点击底部 看剧 栏目 一、创建小程序组件 二、代码 1、WXML <view class"swiper-wrapper" style"background-image:url(/asset/image/hot-banner.jpg);background-size: 100% 100%;">…

android 15

https://android-developers.googleblog.com/2024/02/first-developer-preview-android15.html android 15的预览版出了&#xff0c;这个版本的发布计划大概是这样的&#xff08;大约是今年8月发布最终版本&#xff09; https://developer.android.com/about/versions/15/over…