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

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法:挖坑法&#xff…...

我的求职之路合集

我把我秋招和春招的一些笔面试经验在这里发一下,网友们也可以参考一下。 我的求职之路:(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正式发布

在数字化时代&#xff0c;数据如同新时代的石油&#xff0c;蕴含着巨大的价值。从商业决策到科研探索&#xff0c;从城市规划到环境监测&#xff0c;海量数据的高效处理、精准分析与直观可视化&#xff0c;已成为各行业突破发展瓶颈、实现转型升级的关键所在。历经十年精心打磨…...

LBS 开发微课堂|AI向导接口服务:重塑用户的出行体验

为了让广大开发者 更深入地了解 百度地图开放平台的 技术能力 轻松掌握满满的 技术干货 更加简单地接入 位置服务 我们特别推出了 “位置服务&#xff08;LBS&#xff09;开发微课堂” 系列技术案例 第六期的主题是 《AI向导接口服务的能力与接入方案》 随着地图应…...

AI导航工具我开源了利用node爬取了几百条数据

序言 别因今天的懒惰&#xff0c;让明天的您后悔。输出文章的本意并不是为了得到赞美&#xff0c;而是为了让自己能够学会总结思考&#xff1b;当然&#xff0c;如果有幸能够给到你一点点灵感或者思考&#xff0c;那么我这篇文章的意义将无限放大。 背景 随着AI的发展市面上…...

openstack单机安装

openstack单机安装 网卡配置安装依赖开启虚拟环境修改配置文件 部署openstack部署openstack客户端访问可视化界面Horizon补充 本篇主要讲述Ubuntu2204单机安装openstackstable/2024.2。其他版本的Linux系统或者openstack版本&#xff0c;请参考openstack官网。 网卡配置 需要配…...

Vue3实现小红书瀑布流布局任意组件动态更新页面方法实践

思路 1.首先定义一个瀑布流容器&#xff0c;它的高度暂定&#xff08;后面会更新&#xff09;。把需要布局的组件&#xff08;这里叫做waterfall-item&#xff09;放在瀑布流容器里面渲染出来。使用绝对定位&#xff08;position: absolute&#xff09;&#xff0c;把它移到屏幕…...

深度学习项目--基于LSTM的糖尿病预测探究(pytorch实现)

&#x1f368; 本文为&#x1f517;365天深度学习训练营 中的学习记录博客&#x1f356; 原作者&#xff1a;K同学啊 前言 LSTM模型一直是一个很经典的模型&#xff0c;一般用于序列数据预测&#xff0c;这个可以很好的挖掘数据上下文信息&#xff0c;本文将使用LSTM进行糖尿病…...

Next.js 实战 (十):中间件的魅力,打造更快更安全的应用

什么是中间件&#xff1f; 在 Next.js 中&#xff0c;中间件&#xff08;Middleware&#xff09;是一种用于处理每个传入请求的功能。它允许你在请求到达页面之前对其进行修改或响应。 通过中间件&#xff0c;你可以实现诸如日志记录、身份验证、重定向、CORS配置、压缩等任务…...

python+playwright自动化测试(四):元素操作(键盘鼠标事件)、文件上传

目录 鼠标事件 悬停 移动 按键 点击 滚轮操作 拖拽 键盘事件 输入文本内容 type输入内容 fill输入内容 按键操作press 文件上传 下拉选/单选框/复选框 滚动条操作 鼠标事件 悬停 page.get_by_text(设置,exactTrue).nth(1).hover() 移动 page.mouse.move(x33…...

【论文+源码】Diffusion-LM 改进了可控文本生成

这篇论文探讨了如何在不重新训练的情况下控制语言模型&#xff08;LM&#xff09;的行为&#xff0c;这是自然语言生成中的一个重大开放问题。尽管近期一些研究在控制简单句子属性&#xff08;如情感&#xff09;方面取得了成功&#xff0c;但在复杂的细粒度控制&#xff08;如…...

双目立体校正和Q矩阵

立体校正 对两个摄像机的图像平面重投影&#xff0c;使二者位于同一平面&#xff0c;而且左右图像的行对准。 Bouguet 该算法需要用到双目标定后外参(R&#xff0c;T) 从上图中可以看出&#xff0c;该算法主要分为两步&#xff1a; 使成像平面共面 这个办法很直观&#xff…...

vscode 自用插件

vscode按住ctrl鼠标左键无法跟踪跳转方法名&#xff0c;装这些插件就可以 vscode-elm-jump:常规的代码跳转定义 Vue CSS Peek:跳转css定义 vue-helper:变量函数只跳转定义 Vetur 代码提示 Baidu Comate 自动帮你写console.log Turbo Console Log: ctrl alt l 选中变量之后&am…...

OpenCV:在图像中添加高斯噪声、胡椒噪声

目录 在图像中添加高斯噪声 高斯噪声的特性 添加高斯噪声的实现 给图像添加胡椒噪声 实现胡椒噪声的步骤 相关阅读 OpenCV&#xff1a;图像处理中的低通滤波-CSDN博客 OpenCV&#xff1a;高通滤波之索贝尔、沙尔和拉普拉斯-CSDN博客 OpenCV&#xff1a;图像滤波、卷积与…...

DuckDB:Golang操作DuckDB实战案例

DuckDB是一个嵌入式SQL数据库引擎。它与众所周知的SQLite非常相似&#xff0c;但它是为olap风格的工作负载设计的。DuckDB支持各种数据类型和SQL特性。凭借其在以内存为中心的环境中处理高速分析的能力&#xff0c;它迅速受到数据科学家和分析师的欢迎。在这篇博文中&#xff0…...

MySQL入门(数据库、数据表、数据、字段的操作以及查询相关sql语法)

天行健&#xff0c;君子以自强不息&#xff1b;地势坤&#xff0c;君子以厚德载物。 每个人都有惰性&#xff0c;但不断学习是好好生活的根本&#xff0c;共勉&#xff01; 文章均为学习整理笔记&#xff0c;分享记录为主&#xff0c;如有错误请指正&#xff0c;共同学习进步。…...

【根据当天日期输出明天的日期(需对闰年做判定)。】2022-5-15

缘由根据当天日期输出明天的日期(需对闰年做判定)。日期类型结构体如下&#xff1a; struct data{ int year; int month; int day;};-编程语言-CSDN问答 struct mdata{ int year; int month; int day; }mdata; int 天数(int year, int month) {switch (month){case 1: case 3:…...

Ubuntu系统下交叉编译openssl

一、参考资料 OpenSSL&&libcurl库的交叉编译 - hesetone - 博客园 二、准备工作 1. 编译环境 宿主机&#xff1a;Ubuntu 20.04.6 LTSHost&#xff1a;ARM32位交叉编译器&#xff1a;arm-linux-gnueabihf-gcc-11.1.0 2. 设置交叉编译工具链 在交叉编译之前&#x…...

ES6从入门到精通:前言

ES6简介 ES6&#xff08;ECMAScript 2015&#xff09;是JavaScript语言的重大更新&#xff0c;引入了许多新特性&#xff0c;包括语法糖、新数据类型、模块化支持等&#xff0c;显著提升了开发效率和代码可维护性。 核心知识点概览 变量声明 let 和 const 取代 var&#xf…...

1688商品列表API与其他数据源的对接思路

将1688商品列表API与其他数据源对接时&#xff0c;需结合业务场景设计数据流转链路&#xff0c;重点关注数据格式兼容性、接口调用频率控制及数据一致性维护。以下是具体对接思路及关键技术点&#xff1a; 一、核心对接场景与目标 商品数据同步 场景&#xff1a;将1688商品信息…...

ESP32读取DHT11温湿度数据

芯片&#xff1a;ESP32 环境&#xff1a;Arduino 一、安装DHT11传感器库 红框的库&#xff0c;别安装错了 二、代码 注意&#xff0c;DATA口要连接在D15上 #include "DHT.h" // 包含DHT库#define DHTPIN 15 // 定义DHT11数据引脚连接到ESP32的GPIO15 #define D…...

oracle与MySQL数据库之间数据同步的技术要点

Oracle与MySQL数据库之间的数据同步是一个涉及多个技术要点的复杂任务。由于Oracle和MySQL的架构差异&#xff0c;它们的数据同步要求既要保持数据的准确性和一致性&#xff0c;又要处理好性能问题。以下是一些主要的技术要点&#xff1a; 数据结构差异 数据类型差异&#xff…...

SpringBoot+uniapp 的 Champion 俱乐部微信小程序设计与实现,论文初版实现

摘要 本论文旨在设计并实现基于 SpringBoot 和 uniapp 的 Champion 俱乐部微信小程序&#xff0c;以满足俱乐部线上活动推广、会员管理、社交互动等需求。通过 SpringBoot 搭建后端服务&#xff0c;提供稳定高效的数据处理与业务逻辑支持&#xff1b;利用 uniapp 实现跨平台前…...

.Net Framework 4/C# 关键字(非常用,持续更新...)

一、is 关键字 is 关键字用于检查对象是否于给定类型兼容,如果兼容将返回 true,如果不兼容则返回 false,在进行类型转换前,可以先使用 is 关键字判断对象是否与指定类型兼容,如果兼容才进行转换,这样的转换是安全的。 例如有:首先创建一个字符串对象,然后将字符串对象隐…...

优选算法第十二讲:队列 + 宽搜 优先级队列

优选算法第十二讲&#xff1a;队列 宽搜 && 优先级队列 1.N叉树的层序遍历2.二叉树的锯齿型层序遍历3.二叉树最大宽度4.在每个树行中找最大值5.优先级队列 -- 最后一块石头的重量6.数据流中的第K大元素7.前K个高频单词8.数据流的中位数 1.N叉树的层序遍历 2.二叉树的锯…...

Pinocchio 库详解及其在足式机器人上的应用

Pinocchio 库详解及其在足式机器人上的应用 Pinocchio (Pinocchio is not only a nose) 是一个开源的 C 库&#xff0c;专门用于快速计算机器人模型的正向运动学、逆向运动学、雅可比矩阵、动力学和动力学导数。它主要关注效率和准确性&#xff0c;并提供了一个通用的框架&…...