当前位置: 首页 > news >正文

【代码随想录二刷】Day16-二叉树-C++

代码随想录二刷Day16

每日任务

104.二叉树的最大深度
559.n叉树的最大深度
111.二叉树的最小深度
222.完全二叉树的节点个数
语言:C++

104. 二叉树的最大深度

链接:https://leetcode.cn/problems/maximum-depth-of-binary-tree/
递归法(前序遍历)

class Solution {
public:int res = 0;//depth代表当前root所在层的深度void getDepth(TreeNode* root, int depth){res = res > depth ? res : depth;if(root->left == NULL && root->right == NULL) return; //中//左if(root->left){depth++;getDepth(root->left, depth);depth--;}//右if(root->right){depth++;getDepth(root->right, depth);depth--;}}int maxDepth(TreeNode* root) {if(root == NULL) return res;getDepth(root, 1);return res;}
};

递归法(后序遍历)

class Solution {
public:int getDepth(TreeNode* root){if(root == NULL) return 0;int left = getDepth(root->left); //左int right = getDepth(root->right); //右return 1 + max(left, right); //中}int maxDepth(TreeNode* root) {return getDepth(root);}
};

迭代法(层序遍历)

class Solution {
public:int maxDepth(TreeNode* root) {int res = 0;if(root == NULL) return res;queue<TreeNode*> que;que.push(root);while(!que.empty()){int n = que.size();res++;for(int i = 0; i < n; i++){TreeNode* cur = que.front();que.pop();if(cur->left) que.push(cur->left);if(cur->right) que.push(cur->right);}}return res;}
};

559. n叉树的最大深度

链接:https://leetcode.cn/problems/maximum-depth-of-n-ary-tree/
递归法

class Solution {
public:int getDepth(Node* root){if(root == NULL) return 0;int res = 1;for(int i = 0; i < root->children.size(); i++){int depth = getDepth(root->children[i]) + 1;res = res > depth ? res : depth;}return res;}int maxDepth(Node* root) {return getDepth(root);}
};

迭代法(层序遍历)

class Solution {
public:int maxDepth(Node* root) {int res = 0;if(root == NULL) return res;queue<Node*> que;que.push(root);while(!que.empty()){int n = que.size();res++;for(int i = 0; i < n; i++){Node* cur = que.front();que.pop();for(int j = 0; j < cur->children.size(); j++){que.push(cur->children[j]);}}}return res;}
};

111. 二叉树的最小深度

链接:https://leetcode.cn/problems/minimum-depth-of-binary-tree/
递归法(前序遍历)

class Solution {
public:int res = INT_MAX;//depth代表root所在层的深度void getDepth(TreeNode* root, int depth){if(root == NULL) return;if(root->left == NULL && root->right == NULL){res = min(depth, res);return;}//中没有处理逻辑//左if(root->left){depth++;getDepth(root->left, depth);depth--;}//右if(root->right){depth++;getDepth(root->right, depth);depth--;}}int minDepth(TreeNode* root) {if(root == NULL) return 0;getDepth(root, 1);return res;}
};

递归法(后序遍历)

class Solution {
public:int getDepth(TreeNode* root){if(root == NULL) return 0;int left = getDepth(root->left); //左int right = getDepth(root->right); //右if(root->left == NULL && root->right != NULL) return right + 1;if(root->left != NULL && root->right == NULL) return left + 1;return 1 + min(left, right); //中}int minDepth(TreeNode* root) {return getDepth(root);}
};

迭代法(层序遍历)

class Solution {
public:int minDepth(TreeNode* root) {int res = 0;if(root == NULL) return res;queue<TreeNode*> que;que.push(root);while(!que.empty()){int n = que.size();res++;for(int i = 0; i < n; i++){TreeNode* cur = que.front();que.pop();if(!cur->left && !cur->right) return res;if(cur->left) que.push(cur->left);if(cur->right) que.push(cur->right);}}return res;}
};

222. 完全二叉树的节点个数

链接:https://leetcode.cn/problems/count-complete-tree-nodes/
普通二叉树(递归-后序遍历)

class Solution {
public:int getNumber(TreeNode* root){if(root == NULL) return 0;if(root->left == NULL && root->right == NULL) return 1;int left = getNumber(root->left);int right = getNumber(root->right);return left + right + 1;}int countNodes(TreeNode* root) {if(root == NULL) return 0;return getNumber(root);}
};

普通二叉树(迭代-层序遍历)

class Solution {
public:int countNodes(TreeNode* root) {if(root == NULL) return 0;queue<TreeNode*> que;que.push(root);int res = 0;while(!que.empty()){int n = que.size();res += n;for(int i = 0; i < n; i++){TreeNode* cur = que.front();que.pop();if(cur->left) que.push(cur->left);if(cur->right) que.push(cur->right);}}return res;}
};

完全二叉树
① 满二叉树:2^树深度-1
② 最后一层叶子节点没满:分别递归左孩子和右孩子,一定会有某个左孩子或右孩子为满二叉树

class Solution {
public:int countNodes(TreeNode* root) {if(root == NULL) return 0;int left = 0;int right = 0;TreeNode* cur = root;while(cur->left){cur = cur->left;left++;}cur = root;while(cur->right){cur = cur->right;right++;}if(left == right){return (2 << left) - 1;}return countNodes(root->left) + countNodes(root->right) + 1;}
};

相关文章:

【代码随想录二刷】Day16-二叉树-C++

代码随想录二刷Day16 每日任务 104.二叉树的最大深度 559.n叉树的最大深度 111.二叉树的最小深度 222.完全二叉树的节点个数 语言&#xff1a;C 104. 二叉树的最大深度 链接&#xff1a;https://leetcode.cn/problems/maximum-depth-of-binary-tree/ 递归法&#xff08;前序…...

Lecture5 实现线性回归(Linear Regression with PyTorch)

目录 1 Pytorch实现线性回归 1.1 实现思路 1.2 完整代码 2 各部分代码逐行详解 2.1 准备数据集 2.2 设计模型 2.2.1 代码 2.2.2 代码逐行详解 2.2.3 疑难点解答 2.3 构建损失函数和优化器 2.4 训练周期 2.5 测试结果 3 线性回归中常用优化器 1 Pytorch实现线性回归…...

Python与Matlab svd分解的差异

1.差异说明 Matlab和Python的NumPy库中的SVD函数(np.linalg.svd)都是用来对矩阵进行奇异值分解&#xff08;SVD&#xff09;的函数&#xff0c;但它们在默认参数和返回结果方面有一些差异。 在Matlab中&#xff0c;SVD函数的默认行为是计算矩阵的完整SVD&#xff0c;即对于一…...

2023年光模块行业发展趋势及未来前景

随着数字化时代的到来&#xff0c;互联网行业的快速发展&#xff0c;网络通信设备行业的发展也在逐渐加速。光模块作为网络设备的重要组成部分&#xff0c;也在不断创新和发展。那么&#xff0c;光模块行业的未来发展趋势又是怎样的呢&#xff1f;接下来就跟着易天光通信&#…...

Sysmac Studio使用Tortoise和Git实现版本控制

Sysmac Studio使用Tortoise和Git实现版本控制实验时间&#xff1a;2022/11/16 实验软件&#xff1a;Sysmac Studio(1.52&#xff0c;需要软件授权支持版本控制)、Git(2.38.1)、Tortoise(2.13.0)、gitee(代码仓库) 实验目的&#xff1a;Sysmac Studio实现版本控制、多人同时开…...

Intent 和 Bundle 传值的区别

文章目录1、使用上1.1 Intent 方式1.2 Bundle 方式2、为什么 Bundle 使用 ArrayMap 而不是 Hashmap 实现呢&#xff1f;1、使用上 1.1 Intent 方式 举例&#xff1a;将数据从页面 A 传递到 B&#xff0c;然后再传递到 CA 页面&#xff1a; Intent intentnew Intent(MainActi…...

TypeScript 初步

一、TypeScript是什么&#xff1f; Typed JavaScript at Any Scale: 添加了类型系统的JavaScript&#xff0c;使用于任何规模的项目。 两个重要特点&#xff1a; 类型系统 任何规模 中文官网&#xff1a;文档简介 TypeScript中文网 TypeScript——JavaScript的超集 TypeS…...

leaflet 添加zoomslider,控制zoom放大缩小(074)

第074个 点击查看专栏目录 本示例的目的是介绍演示如何在vue+leaflet中使用zoomslider,相比于普通的zoom控件,这个更加形象,更加具体些。 直接复制下面的 vue+leaflet源代码,操作2分钟即可运行实现效果 文章目录 示例效果配置方式示例源代码(共65行)相关API参考:专栏目…...

10分钟学会python对接【OpenAI API篇】

今天学习 OpenAI API&#xff0c;你将能够访问 OpenAI 的强大模型&#xff0c;例如用于自然语言的 GPT-3、用于将自然语言翻译为代码的 Codex 以及用于创建和编辑原始图像的 DALL-E。 首先获取生成 API 密钥 在我们开始使用 OpenAI API 之前&#xff0c;我们需要登录我们的 Op…...

2023美赛必须注意事项

文章目录首页部分要求竞赛期间题目查看题目下载论文要求比赛提示控制号提交解决方案更多注意事项首页部分要求 具体如下&#xff1a; 我提取一些关键词如下&#xff1a; 第一页&#xff1a;摘要页字体要求&#xff1a;12点的 Times New Roman 字体请勿在此页面或任何页面上…...

基于微信小程序的智能招聘小程序

文末联系获取源码 开发语言&#xff1a;Java 框架&#xff1a;ssm JDK版本&#xff1a;JDK1.8 服务器&#xff1a;tomcat7 数据库&#xff1a;mysql 5.7/8.0 数据库工具&#xff1a;Navicat11 开发软件&#xff1a;eclipse/myeclipse/idea Maven包&#xff1a;Maven3.3.9 浏览器…...

Java文件操作和I/O

Java 流(Stream)、文件(File)和IOJava.io 包几乎包含了所有操作输入、输出需要的类。所有这些流类代表了输入源和输出目标。Java.io 包中的流支持很多种格式&#xff0c;比如&#xff1a;基本类型、对象、本地化字符集等等。一个流可以理解为一个数据的序列。输入流表示从一个源…...

QT项目_RPC(进程间通讯)

QT项目_RPC(进程间通讯) 前言&#xff1a; 两个进程间通信、或是说两个应用程序之间通讯。实际情况是在QT开发的一个项目中&#xff0c;里面包含两个子程序&#xff0c;子程序有单独的界面和应用逻辑&#xff0c;这两个子程序跑起来之后需要一些数据的交互&#xff0c;例如&…...

移动硬盘文件丢失怎么恢复?

在我们的日常工作、学习和生活都离不开各种数据。每天都会接收或处理各种数据&#xff0c;尤其是做设计、自媒体、多媒体设计的人。移动硬盘成为我们常备的存储工具&#xff0c;但有使用就会伴随着意外情况的发生&#xff0c;这将导致移动硬盘上数据的丢失&#xff0c;比如误删…...

什么是同步整流和异步整流

在设计降压型DCDC电路的时候&#xff0c;经常会听到同步整流&#xff08;synchronous&#xff09;和异步整流&#xff08;asynchronous&#xff09;。那么什么是同步整流&#xff0c;什么是异步整流呢从这两种电路的拓扑来看&#xff0c;异步整流型外围有一个续流二极管&#x…...

关于PYTHON Enclosing 的一个小问题

问题分析 以下是一段每隔半小时重复执行测试用例的脚本&#xff0c;func是传入的测试函数&#xff0c;在执行func前后&#xff0c;会打印操作次数 def repeat(func, action):try:log.info(u******开始并发%s****** % action)thread_list []for i in range(repeat_count):def…...

LabVIEW错误-2147220623:最大内存块属性不存在

LabVIEW错误-2147220623&#xff1a;最大内存块属性不存在在使用NI Linux实时操作系统目标中&#xff0c;使用系统属性节点和分布式系统管理器&#xff08;DSM&#xff09;&#xff0c;但遇到一些问题&#xff1a;它未正确报告系统上的可用物理内存量。在NI Linux实时系统上出现…...

图的总复习

一、图的定义Graph 图是由顶点vertex集合及顶点间关系集合组成的一种数据结构&#xff1a; 顶点的集合 和 边的集合 二、无向图 用&#xff08;x,y&#xff09;表示两个顶点x和y之间的一条边&#xff08;edge&#xff09; 边是无方向的 N{V&#xff0c;E}&#xff0c;V{0…...

测试流程记录

1&#xff0c;需求评审 2&#xff0c;技术方案评审 3&#xff0c;编写测试用例 编写需求分析 编写测试用例 编写冒烟case 4&#xff0c;用例评审 5&#xff0c;提测 提测前给开发执行冒烟case 6&#xff0c;测试 测试完成前约产品验收时间 7&#xff0c;验收 跟进验收问题…...

Mysql主从架构与实例

mysql的主从架构 MySQL主从架构是一种常见的数据库高可用性解决方案&#xff0c;它通常由一个主数据库和多个从数据库组成。主数据库用于处理写入请求和读取请求&#xff0c;从数据库则用于处理只读请求。 在主从架构中&#xff0c;主数据库记录所有数据更改并将这些更改同步…...

[2025CVPR]DeepVideo-R1:基于难度感知回归GRPO的视频强化微调框架详解

突破视频大语言模型推理瓶颈,在多个视频基准上实现SOTA性能 一、核心问题与创新亮点 1.1 GRPO在视频任务中的两大挑战 ​安全措施依赖问题​ GRPO使用min和clip函数限制策略更新幅度,导致: 梯度抑制:当新旧策略差异过大时梯度消失收敛困难:策略无法充分优化# 传统GRPO的梯…...

RocketMQ延迟消息机制

两种延迟消息 RocketMQ中提供了两种延迟消息机制 指定固定的延迟级别 通过在Message中设定一个MessageDelayLevel参数&#xff0c;对应18个预设的延迟级别指定时间点的延迟级别 通过在Message中设定一个DeliverTimeMS指定一个Long类型表示的具体时间点。到了时间点后&#xf…...

shell脚本--常见案例

1、自动备份文件或目录 2、批量重命名文件 3、查找并删除指定名称的文件&#xff1a; 4、批量删除文件 5、查找并替换文件内容 6、批量创建文件 7、创建文件夹并移动文件 8、在文件夹中查找文件...

STM32标准库-DMA直接存储器存取

文章目录 一、DMA1.1简介1.2存储器映像1.3DMA框图1.4DMA基本结构1.5DMA请求1.6数据宽度与对齐1.7数据转运DMA1.8ADC扫描模式DMA 二、数据转运DMA2.1接线图2.2代码2.3相关API 一、DMA 1.1简介 DMA&#xff08;Direct Memory Access&#xff09;直接存储器存取 DMA可以提供外设…...

如何在看板中有效管理突发紧急任务

在看板中有效管理突发紧急任务需要&#xff1a;设立专门的紧急任务通道、重新调整任务优先级、保持适度的WIP&#xff08;Work-in-Progress&#xff09;弹性、优化任务处理流程、提高团队应对突发情况的敏捷性。其中&#xff0c;设立专门的紧急任务通道尤为重要&#xff0c;这能…...

在鸿蒙HarmonyOS 5中使用DevEco Studio实现录音机应用

1. 项目配置与权限设置 1.1 配置module.json5 {"module": {"requestPermissions": [{"name": "ohos.permission.MICROPHONE","reason": "录音需要麦克风权限"},{"name": "ohos.permission.WRITE…...

SAP学习笔记 - 开发26 - 前端Fiori开发 OData V2 和 V4 的差异 (Deepseek整理)

上一章用到了V2 的概念&#xff0c;其实 Fiori当中还有 V4&#xff0c;咱们这一章来总结一下 V2 和 V4。 SAP学习笔记 - 开发25 - 前端Fiori开发 Remote OData Service(使用远端Odata服务)&#xff0c;代理中间件&#xff08;ui5-middleware-simpleproxy&#xff09;-CSDN博客…...

LINUX 69 FTP 客服管理系统 man 5 /etc/vsftpd/vsftpd.conf

FTP 客服管理系统 实现kefu123登录&#xff0c;不允许匿名访问&#xff0c;kefu只能访问/data/kefu目录&#xff0c;不能查看其他目录 创建账号密码 useradd kefu echo 123|passwd -stdin kefu [rootcode caozx26420]# echo 123|passwd --stdin kefu 更改用户 kefu 的密码…...

解读《网络安全法》最新修订,把握网络安全新趋势

《网络安全法》自2017年施行以来&#xff0c;在维护网络空间安全方面发挥了重要作用。但随着网络环境的日益复杂&#xff0c;网络攻击、数据泄露等事件频发&#xff0c;现行法律已难以完全适应新的风险挑战。 2025年3月28日&#xff0c;国家网信办会同相关部门起草了《网络安全…...

MacOS下Homebrew国内镜像加速指南(2025最新国内镜像加速)

macos brew国内镜像加速方法 brew install 加速formula.jws.json下载慢加速 &#x1f37a; 最新版brew安装慢到怀疑人生&#xff1f;别怕&#xff0c;教你轻松起飞&#xff01; 最近Homebrew更新至最新版&#xff0c;每次执行 brew 命令时都会自动从官方地址 https://formulae.…...