LeetCode 力扣热题100 二叉树的直径
class Solution {
public:// 定义一个变量 `maxd`,用于存储当前二叉树的最大直径。int maxd = 0; // 主函数,计算二叉树的直径。int diameterOfBinaryTree(TreeNode* root) {// 调用 `maxDepth` 函数进行递归计算,并更新 `maxd`。maxDepth(root);// 返回计算得到的最大直径。return maxd;}// 定义 `maxDepth` 函数,计算二叉树的深度,同时更新直径。public:int maxDepth(TreeNode* root) {// 如果当前节点为空,则返回深度为 0。if (root == nullptr) {return 0;}// 递归计算左子树的深度。int l_depth = maxDepth(root->left);// 递归计算右子树的深度。int r_depth = maxDepth(root->right);// 更新最大直径:通过当前节点的左右子树深度之和来计算路径长度。maxd = max(l_depth + r_depth, maxd);// 返回当前节点的最大深度(左右子树深度的最大值 + 当前节点)。return max(l_depth, r_depth) + 1;}
};
假设我们有一个二叉树如下:
1
/ \
2 3
/ \
4 5
运行过程:
1. 初始化阶段:
• maxd = 0
• 调用 diameterOfBinaryTree(root),其中 root 指向节点 1。
2. 递归展开 maxDepth(root):
• 以节点 1 为根,计算左子树和右子树的深度。
左子树递归(以 2 为根):
• 调用 maxDepth(root->left),进入节点 2。
左子树的左子树递归(以 4 为根):
• 调用 maxDepth(root->left->left),进入节点 4。
• 节点 4 的左右子树为空:
• 调用 maxDepth(root->left->left->left) 返回 0。
• 调用 maxDepth(root->left->left->right) 返回 0。
• 通过节点 4 的路径长度为 0 + 0 = 0。
• maxd = max(0, maxd) = 0。
• 返回节点 4 的深度:max(0, 0) + 1 = 1。
左子树的右子树递归(以 5 为根):
• 调用 maxDepth(root->left->right),进入节点 5。
• 节点 5 的左右子树为空:
• 调用 maxDepth(root->left->right->left) 返回 0。
• 调用 maxDepth(root->left->right->right) 返回 0。
• 通过节点 5 的路径长度为 0 + 0 = 0。
• maxd = max(0, maxd) = 0。
• 返回节点 5 的深度:max(0, 0) + 1 = 1。
回到节点 2:
• 左子树深度为 1(节点 4)。
• 右子树深度为 1(节点 5)。
• 通过节点 2 的路径长度为 1 + 1 = 2。
• maxd = max(2, maxd) = 2。
• 返回节点 2 的深度:max(1, 1) + 1 = 2。
右子树递归(以 3 为根):
• 调用 maxDepth(root->right),进入节点 3。
• 节点 3 的左右子树为空:
• 调用 maxDepth(root->right->left) 返回 0。
• 调用 maxDepth(root->right->right) 返回 0。
• 通过节点 3 的路径长度为 0 + 0 = 0。
• maxd = max(0, maxd) = 2。
• 返回节点 3 的深度:max(0, 0) + 1 = 1。
回到节点 1:
• 左子树深度为 2(节点 2)。
• 右子树深度为 1(节点 3)。
• 通过节点 1 的路径长度为 2 + 1 = 3。
• maxd = max(3, maxd) = 3。
• 返回节点 1 的深度:max(2, 1) + 1 = 3。
结果:
• 最终,maxd = 3,表示二叉树的最大直径为 3。
• 返回值为 3。
递归总结:
• 每次递归调用时,我们计算左右子树的深度,并利用它们更新全局变量 maxd。
• maxDepth 返回的是当前节点的深度,而 maxd 更新的是路径长度(左深度 + 右深度)。
相关文章:
LeetCode 力扣热题100 二叉树的直径
class Solution { public:// 定义一个变量 maxd,用于存储当前二叉树的最大直径。int maxd 0; // 主函数,计算二叉树的直径。int diameterOfBinaryTree(TreeNode* root) {// 调用 maxDepth 函数进行递归计算,并更新 maxd。maxDepth(root);// …...
【图文详解】lnmp架构搭建Discuz论坛
安装部署LNMP 系统及软件版本信息 软件名称版本nginx1.24.0mysql5.7.41php5.6.27安装nginx 我们对Markdown编辑器进行了一些功能拓展与语法支持,除了标准的Markdown编辑器功能,我们增加了如下几点新功能,帮助你用它写博客: 关闭防火墙 systemctl stop firewalld &&a…...
小哆啦解题记:整数转罗马数字
小哆啦解题记:整数转罗马数字 小哆啦开始力扣每日一题的第十四天 https://leetcode.cn/problems/integer-to-roman/submissions/595220508/ 第一章:神秘的任务 一天,哆啦A梦接到了一项任务——将一个整数转换为罗马数字。他心想:…...
【Java数据结构】排序
【Java数据结构】排序 一、排序1.1 排序的概念1.2 排序的稳定性1.3 内部排序和外部排序1.3.1 内部排序1.3.2 外部排序 二、插入排序2.1 直接插入排序2.2 希尔排序 三、选择排序3.1 选择排序3.2 堆排序 四、交换排序4.1 冒泡排序4.2 快速排序Hoare法:挖坑法ÿ…...
我的求职之路合集
我把我秋招和春招的一些笔面试经验在这里发一下,网友们也可以参考一下。 我的求职之路:(1)如何谈自己的缺点 我的求职之路:(2)找工作时看重的点 我的求职之路:(3&…...
数据结构(四) B树/跳表
目录 1. LRU 2. B树 3. 跳表 1. LRU: 1.1 概念: 最近最少使用算法, 就是cache缓存的算法. 因为cache(位于内存和cpu之间的存储设备)是一种容量有限的缓存, 有新的数据进入就需要将原本的数据进行排出. 1.2 LRU cache实现: #include <iostream> #include <list>…...
Arcgis国产化替代:Bigemap Pro正式发布
在数字化时代,数据如同新时代的石油,蕴含着巨大的价值。从商业决策到科研探索,从城市规划到环境监测,海量数据的高效处理、精准分析与直观可视化,已成为各行业突破发展瓶颈、实现转型升级的关键所在。历经十年精心打磨…...
LBS 开发微课堂|AI向导接口服务:重塑用户的出行体验
为了让广大开发者 更深入地了解 百度地图开放平台的 技术能力 轻松掌握满满的 技术干货 更加简单地接入 位置服务 我们特别推出了 “位置服务(LBS)开发微课堂” 系列技术案例 第六期的主题是 《AI向导接口服务的能力与接入方案》 随着地图应…...
AI导航工具我开源了利用node爬取了几百条数据
序言 别因今天的懒惰,让明天的您后悔。输出文章的本意并不是为了得到赞美,而是为了让自己能够学会总结思考;当然,如果有幸能够给到你一点点灵感或者思考,那么我这篇文章的意义将无限放大。 背景 随着AI的发展市面上…...
openstack单机安装
openstack单机安装 网卡配置安装依赖开启虚拟环境修改配置文件 部署openstack部署openstack客户端访问可视化界面Horizon补充 本篇主要讲述Ubuntu2204单机安装openstackstable/2024.2。其他版本的Linux系统或者openstack版本,请参考openstack官网。 网卡配置 需要配…...
Vue3实现小红书瀑布流布局任意组件动态更新页面方法实践
思路 1.首先定义一个瀑布流容器,它的高度暂定(后面会更新)。把需要布局的组件(这里叫做waterfall-item)放在瀑布流容器里面渲染出来。使用绝对定位(position: absolute),把它移到屏幕…...
深度学习项目--基于LSTM的糖尿病预测探究(pytorch实现)
🍨 本文为🔗365天深度学习训练营 中的学习记录博客🍖 原作者:K同学啊 前言 LSTM模型一直是一个很经典的模型,一般用于序列数据预测,这个可以很好的挖掘数据上下文信息,本文将使用LSTM进行糖尿病…...
Next.js 实战 (十):中间件的魅力,打造更快更安全的应用
什么是中间件? 在 Next.js 中,中间件(Middleware)是一种用于处理每个传入请求的功能。它允许你在请求到达页面之前对其进行修改或响应。 通过中间件,你可以实现诸如日志记录、身份验证、重定向、CORS配置、压缩等任务…...
python+playwright自动化测试(四):元素操作(键盘鼠标事件)、文件上传
目录 鼠标事件 悬停 移动 按键 点击 滚轮操作 拖拽 键盘事件 输入文本内容 type输入内容 fill输入内容 按键操作press 文件上传 下拉选/单选框/复选框 滚动条操作 鼠标事件 悬停 page.get_by_text(设置,exactTrue).nth(1).hover() 移动 page.mouse.move(x33…...
【论文+源码】Diffusion-LM 改进了可控文本生成
这篇论文探讨了如何在不重新训练的情况下控制语言模型(LM)的行为,这是自然语言生成中的一个重大开放问题。尽管近期一些研究在控制简单句子属性(如情感)方面取得了成功,但在复杂的细粒度控制(如…...
双目立体校正和Q矩阵
立体校正 对两个摄像机的图像平面重投影,使二者位于同一平面,而且左右图像的行对准。 Bouguet 该算法需要用到双目标定后外参(R,T) 从上图中可以看出,该算法主要分为两步: 使成像平面共面 这个办法很直观ÿ…...
vscode 自用插件
vscode按住ctrl鼠标左键无法跟踪跳转方法名,装这些插件就可以 vscode-elm-jump:常规的代码跳转定义 Vue CSS Peek:跳转css定义 vue-helper:变量函数只跳转定义 Vetur 代码提示 Baidu Comate 自动帮你写console.log Turbo Console Log: ctrl alt l 选中变量之后&am…...
OpenCV:在图像中添加高斯噪声、胡椒噪声
目录 在图像中添加高斯噪声 高斯噪声的特性 添加高斯噪声的实现 给图像添加胡椒噪声 实现胡椒噪声的步骤 相关阅读 OpenCV:图像处理中的低通滤波-CSDN博客 OpenCV:高通滤波之索贝尔、沙尔和拉普拉斯-CSDN博客 OpenCV:图像滤波、卷积与…...
DuckDB:Golang操作DuckDB实战案例
DuckDB是一个嵌入式SQL数据库引擎。它与众所周知的SQLite非常相似,但它是为olap风格的工作负载设计的。DuckDB支持各种数据类型和SQL特性。凭借其在以内存为中心的环境中处理高速分析的能力,它迅速受到数据科学家和分析师的欢迎。在这篇博文中࿰…...
MySQL入门(数据库、数据表、数据、字段的操作以及查询相关sql语法)
天行健,君子以自强不息;地势坤,君子以厚德载物。 每个人都有惰性,但不断学习是好好生活的根本,共勉! 文章均为学习整理笔记,分享记录为主,如有错误请指正,共同学习进步。…...
eNSP-Cloud(实现本地电脑与eNSP内设备之间通信)
说明: 想象一下,你正在用eNSP搭建一个虚拟的网络世界,里面有虚拟的路由器、交换机、电脑(PC)等等。这些设备都在你的电脑里面“运行”,它们之间可以互相通信,就像一个封闭的小王国。 但是&#…...
手游刚开服就被攻击怎么办?如何防御DDoS?
开服初期是手游最脆弱的阶段,极易成为DDoS攻击的目标。一旦遭遇攻击,可能导致服务器瘫痪、玩家流失,甚至造成巨大经济损失。本文为开发者提供一套简洁有效的应急与防御方案,帮助快速应对并构建长期防护体系。 一、遭遇攻击的紧急应…...
MongoDB学习和应用(高效的非关系型数据库)
一丶 MongoDB简介 对于社交类软件的功能,我们需要对它的功能特点进行分析: 数据量会随着用户数增大而增大读多写少价值较低非好友看不到其动态信息地理位置的查询… 针对以上特点进行分析各大存储工具: mysql:关系型数据库&am…...
【Java学习笔记】Arrays类
Arrays 类 1. 导入包:import java.util.Arrays 2. 常用方法一览表 方法描述Arrays.toString()返回数组的字符串形式Arrays.sort()排序(自然排序和定制排序)Arrays.binarySearch()通过二分搜索法进行查找(前提:数组是…...
Cinnamon修改面板小工具图标
Cinnamon开始菜单-CSDN博客 设置模块都是做好的,比GNOME简单得多! 在 applet.js 里增加 const Settings imports.ui.settings;this.settings new Settings.AppletSettings(this, HTYMenusonichy, instance_id); this.settings.bind(menu-icon, menu…...
C# SqlSugar:依赖注入与仓储模式实践
C# SqlSugar:依赖注入与仓储模式实践 在 C# 的应用开发中,数据库操作是必不可少的环节。为了让数据访问层更加简洁、高效且易于维护,许多开发者会选择成熟的 ORM(对象关系映射)框架,SqlSugar 就是其中备受…...
C++:多态机制详解
目录 一. 多态的概念 1.静态多态(编译时多态) 二.动态多态的定义及实现 1.多态的构成条件 2.虚函数 3.虚函数的重写/覆盖 4.虚函数重写的一些其他问题 1).协变 2).析构函数的重写 5.override 和 final关键字 1&#…...
Golang——6、指针和结构体
指针和结构体 1、指针1.1、指针地址和指针类型1.2、指针取值1.3、new和make 2、结构体2.1、type关键字的使用2.2、结构体的定义和初始化2.3、结构体方法和接收者2.4、给任意类型添加方法2.5、结构体的匿名字段2.6、嵌套结构体2.7、嵌套匿名结构体2.8、结构体的继承 3、结构体与…...
逻辑回归暴力训练预测金融欺诈
简述 「使用逻辑回归暴力预测金融欺诈,并不断增加特征维度持续测试」的做法,体现了一种逐步建模与迭代验证的实验思路,在金融欺诈检测中非常有价值,本文作为一篇回顾性记录了早年间公司给某行做反欺诈预测用到的技术和思路。百度…...
day36-多路IO复用
一、基本概念 (服务器多客户端模型) 定义:单线程或单进程同时监测若干个文件描述符是否可以执行IO操作的能力 作用:应用程序通常需要处理来自多条事件流中的事件,比如我现在用的电脑,需要同时处理键盘鼠标…...
