二叉树的最大深度

二叉树的最大深度

思路:

法一:深搜   也就是递归  要想清楚边界条件

好久没写深搜了 回忆下怎么写。

突然就悟了:

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:int ans=0;int sd=0;int dfs(TreeNode* root)//返回以root为根节点的树的最大深度;{if(root){sd++;int a=dfs(root->left);int b=dfs(root->right);return max(a,b)+1;}else return 0;}int maxDepth(TreeNode* root) {//用深搜试试return dfs(root);}
};
  • 时间复杂度:O(n),其中 n 为二叉树节点的个数。每个节点在递归中只被遍历一次。

法二:广搜

取队头:q.front();

取栈顶:st.top();

怎么控制一层层地拓展呢,加一个sz  维护每次开始拓展一行的时候,队列里的元素个数,这就是这一行的元素个数。用while(sz--)可以一行行拓展。

看代码也可以领悟这一点。

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {queue<TreeNode* > q;//bfs一般用队列来实现int ans=0;int sz=0;void bfs(TreeNode*root){q.push(root);while(!q.empty())//这里一层层的扩展,扩展的次数就是深度{sz=q.size();//当前层有多少个结点。while(sz!=0)//一层层地遍历{auto t=q.front();q.pop();if(t->left) q.push(t->left);if(t->right) q.push(t->right);sz--;}ans++;}}
public:int maxDepth(TreeNode* root) {if(!root) return 0;bfs(root);return ans;}
};

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

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

相关文章

2024年6月 青少年机器人技术等级考试理论综合试卷(二级)

202406 青少年等级考试机器人理论真题二级 第 1 题 如图&#xff0c;这是飞机起飞时的机翼示意图&#xff0c;下列说法正确的是&#xff1f;&#xff08; &#xff09; A&#xff1a;机翼上侧所受的气压为0 B&#xff1a;机翼受到向下的力的作用 C&#xff1a;机翼下侧所受…

基于sklearn的机器学习 — 支持向量机(SVM)

支持向量机&#xff08;SVM&#xff1a;support vector machine&#xff09;另一种功能强大、应用广泛的学习算法&#xff0c;可应用于分类、回归、密度估计、聚类等问题。SVM可以看作是感知器&#xff08;可被视为一种最简单形式的前馈神经网络&#xff0c;是一种二元线性分类…

C++ 特殊类设计

目录 0.前言 1.设计一个不能被拷贝的类 1.1C98实现 1.2C11实现 2.设计一个只能在堆上创建对象的类 3.设计一个只能在栈上创建对象的类 4.设计一个不能被继承的类 4.1C98实现 4.2C11实现 5.设计只能创建一个对象的类&#xff08;单例模式&#xff09; 5.1设计模式简介 5.2单例模…

Jupyter nbextensions安装与使用

这里写自定义目录标题 Jupyter nbextensions安装与使用安装7以下版本&#xff0c;安装插件包推荐使用的插件 Jupyter nbextensions安装与使用 目前&#xff0c;jupyter版本升级到了7以上版本&#xff0c;导致其界面非常难看&#xff0c;因此&#xff0c;为了重回之前的使用界面…

buuctf-crypto

前言 查找资料的时候,意外翻出之前刷的一些ctf题目,算是简单记录一下,当然因为常用typeo去写md文件,所以其中有很多当时记录的图片都失效了,可惜了 题目1:一眼就解密 ZmxhZ3tUSEVfRkxBR19PRl9USElTX1NUUklOR30 base64解密 flag:flag{THE_FLAG_OF_THIS_STRING} 题目2:MD5 …

全球化浪潮下的数据库革新:嘉里物流 TiDB 实践价值的设想

导读 本文来自 TiDB 社区武汉站——嘉里物流架构团队负责人肖飞老师的演讲《嘉里物流 & TiDB 在全球化业务场景中应用设想》。本次分享探讨了嘉里物流在全球化扩展中&#xff0c;将如何通过 TiDB 的强大功能应对海量数据挑战&#xff0c;优化技术架构&#xff0c;并提升决…

【Linux】详解自定义Shell管道 | 构建简易进程池

目录 续&#xff1a;通信 4 种情况 应用场景 1. 自定义 shell 管道 1. 包含头文件 2. 解析命令函数 详细步骤 3. 执行命令函数 4. 主函数 总结 2. 使用管道实现一个简易版本的进程池 代码结构 代码实现 channel.hpp tasks.hpp main.cc 子进程读取任务&#xff…

十九、虚拟机VMware Workstation(CentOSDebian)的安装

目录 &#x1f33b;&#x1f33b; 一、安装 VMware Workstation1.1 安装 VMware Workstation1.2 虚拟机上安装 CentOS1.3 虚拟机安装 Debian 二、配置Debian方便第三方工具远程连接2.1 配置debian2.2 安装远程SSH工具并连接 一、安装 VMware Workstation 官网下载 本地资源库…

你好! Git——企业级开发模型

企业级开发模型&#xff08;6&#xff09; 一、删除远程分支&#xff0c;git branch -a &#xff08;查看所有本地分支与远程分支&#xff09;还能看到已经删除的分支&#xff0c;怎么解决&#xff1f;二、企业级开发流程2.1 企业级开发流程2.2 系统开发环境 三、Git分支设计模…

RabbitMQ面试题汇总

RabbitMQ面试题 一、RabbitMQ基础1. 什么是RabbitMQ&#xff0c;它的基本架构是怎样的&#xff1f;2. RabbitMQ支持哪些协议&#xff1f;3. 说一下AMQP协议&#xff1f;4. 为什么要使用RabbitMQ&#xff1f;5. MQ的应用场景有哪些&#xff1f;6. 解耦、异步、削峰是什么&#x…

购物系统小程序的设计

管理员账户功能包括&#xff1a;系统首页&#xff0c;个人中心&#xff0c;商品分类管理&#xff0c;商品信息管理&#xff0c;特价商品管理&#xff0c;用户管理&#xff0c;留言板管理&#xff0c;订单管理&#xff0c;系统管理 微信端账号功能包括&#xff1a;系统首页&…

uni-app总结

1. <u-form-item label"报废人" ><u--input v-model"model.remark" border"bottom" placeholder"请输入"></u--input> </u-form-item> border"bottom" 报废日期 为了

后端Web开发之Maven

1.java项目构建工具maven介绍 Maven是apache旗下的一个开源项目。Apache软件基金会&#xff0c;成立于1999年7月&#xff0c;是目前世界上最大的最受欢迎的开源&#xff08;源代码开放&#xff09;软件基金会也是一一个专门为支持开源项目而生的非盈利性组织。 apache开源项目…

PDO在CANopen协议同步传输和异步传输

PDO&#xff08;过程数据对象&#xff09;在CANopen协议中有两种主要的传输方式&#xff1a;同步传输和异步传输。这两种方式决定了PDO数据的传输时机和条件。下面分别举例说明这两种传输方式&#xff1a; 1. 同步传输 (Synchronous Transmission) 概念&#xff1a; 在同步传输…

3GPP 4G 5G 主要协议

4G LTE的协议主要是36 series 5G NR的协议主要是38 series

RustScan:开源端口扫描器

RustScan 是一款开源端口扫描器&#xff0c;专为速度和多功能性而设计。 它结合了时尚的界面和随时间推移而适应和改进的能力。 借助 RustScan 的自适应学习功能&#xff0c;该工具不断优化其性能&#xff0c;使其成为最高效的端口扫描器。 在几秒钟内发现开放端口&#xff…

解决端口号被占用问题

第一种&#xff1a; 最简单有效的方法&#xff0c;重启一下电脑&#xff0c;占用此端口的程序就会释放端口。 第二种&#xff1a; 使用命令找到占用端口的程序&#xff0c;把它关闭。 1、打开运行窗口输入&#xff1a;CMD &#xff0c;进入命令窗口。 2、输入&#xff1a;n…

Candance Allegro 入门教程笔记:如何绘制原理图和原理图库?

文章目录 一、用 Capture CIS 17.4 绘制原理图库 Cadence Allegro QQ交流学习裙&#xff1a;173416628 1、凡亿教育的Candance Allegro 17.4基础教程 2、小哥Cadence Allegro 132讲 技巧视频 3、小哥Cadence Allegro 两层板 基础视频 4、小哥Cadence Allegro 四层板 提高视频…

23.10 Django 事务的使用

1. 事务 事务(Transaction): 是一种将多个数据库操作组合成一个单一工作单元的机制. 如果事务中的所有操作都成功完成, 则这些更改将永久保存到数据库中. 如果事务中的某个操作失败, 则整个事务将回滚到事务开始前的状态, 所有的更改都不会被保存到数据库中. 这对于保持数据的…

3.串口(UART)

串口理论部分可看51部分&#xff1a;链接 数据帧 帧头(2字节&#xff0c;例如AA、BB) 数据长度&#xff08;2字节&#xff09; 数据 CRC16校验&#xff08;2字节&#xff09; 帧尾&#xff08;2字节&#xff09; 代码编写 串口一发送命令控制LED灯(PB5、PE5) LED灯、串口、…