当前位置: 首页 > 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;主数据库记录所有数据更改并将这些更改同步…...

微信小程序之bind和catch

这两个呢&#xff0c;都是绑定事件用的&#xff0c;具体使用有些小区别。 官方文档&#xff1a; 事件冒泡处理不同 bind&#xff1a;绑定的事件会向上冒泡&#xff0c;即触发当前组件的事件后&#xff0c;还会继续触发父组件的相同事件。例如&#xff0c;有一个子视图绑定了b…...

《Qt C++ 与 OpenCV:解锁视频播放程序设计的奥秘》

引言:探索视频播放程序设计之旅 在当今数字化时代,多媒体应用已渗透到我们生活的方方面面,从日常的视频娱乐到专业的视频监控、视频会议系统,视频播放程序作为多媒体应用的核心组成部分,扮演着至关重要的角色。无论是在个人电脑、移动设备还是智能电视等平台上,用户都期望…...

Auto-Coder使用GPT-4o完成:在用TabPFN这个模型构建一个预测未来3天涨跌的分类任务

通过akshare库&#xff0c;获取股票数据&#xff0c;并生成TabPFN这个模型 可以识别、处理的格式&#xff0c;写一个完整的预处理示例&#xff0c;并构建一个预测未来 3 天股价涨跌的分类任务 用TabPFN这个模型构建一个预测未来 3 天股价涨跌的分类任务&#xff0c;进行预测并输…...

AirSim/Cosys-AirSim 游戏开发(四)外部固定位置监控相机

这个博客介绍了如何通过 settings.json 文件添加一个无人机外的 固定位置监控相机&#xff0c;因为在使用过程中发现 Airsim 对外部监控相机的描述模糊&#xff0c;而 Cosys-Airsim 在官方文档中没有提供外部监控相机设置&#xff0c;最后在源码示例中找到了&#xff0c;所以感…...

给网站添加live2d看板娘

给网站添加live2d看板娘 参考文献&#xff1a; stevenjoezhang/live2d-widget: 把萌萌哒的看板娘抱回家 (ノ≧∇≦)ノ | Live2D widget for web platformEikanya/Live2d-model: Live2d model collectionzenghongtu/live2d-model-assets 前言 网站环境如下&#xff0c;文章也主…...

离线语音识别方案分析

随着人工智能技术的不断发展&#xff0c;语音识别技术也得到了广泛的应用&#xff0c;从智能家居到车载系统&#xff0c;语音识别正在改变我们与设备的交互方式。尤其是离线语音识别&#xff0c;由于其在没有网络连接的情况下仍然能提供稳定、准确的语音处理能力&#xff0c;广…...

sshd代码修改banner

sshd服务连接之后会收到字符串&#xff1a; SSH-2.0-OpenSSH_9.5 容易被hacker识别此服务为sshd服务。 是否可以通过修改此banner达到让人无法识别此服务的目的呢&#xff1f; 不能。因为这是写的SSH的协议中的。 也就是协议规定了banner必须这么写。 SSH- 开头&#xff0c…...

Mysql故障排插与环境优化

前置知识点 最上层是一些客户端和连接服务&#xff0c;包含本 sock 通信和大多数jiyukehuduan/服务端工具实现的TCP/IP通信。主要完成一些简介处理、授权认证、及相关的安全方案等。在该层上引入了线程池的概念&#xff0c;为通过安全认证接入的客户端提供线程。同样在该层上可…...

node.js的初步学习

那什么是node.js呢&#xff1f; 和JavaScript又是什么关系呢&#xff1f; node.js 提供了 JavaScript的运行环境。当JavaScript作为后端开发语言来说&#xff0c; 需要在node.js的环境上进行当JavaScript作为前端开发语言来说&#xff0c;需要在浏览器的环境上进行 Node.js 可…...

云原生安全实战:API网关Envoy的鉴权与限流详解

&#x1f525;「炎码工坊」技术弹药已装填&#xff01; 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 一、基础概念 1. API网关 作为微服务架构的统一入口&#xff0c;负责路由转发、安全控制、流量管理等核心功能。 2. Envoy 由Lyft开源的高性能云原生…...