LeetCode 热题 100_二叉树的直径(40_543_简单_C++)(二叉树;递归)
LeetCode 热题 100_二叉树的直径(40_543)
- 题目描述:
- 输入输出样例:
- 题解:
- 解题思路:
- 思路一(递归):
- 代码实现
- 代码实现(思路一(递归)):
- 以思路一为例进行调试
题目描述:
给你一棵二叉树的根节点,返回该树的 直径 。
二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。
两节点之间路径的 长度 由它们之间边数表示。
输入输出样例:
示例 1:

输入:root = [1,2,3,4,5]
输出:3
解释:3 ,取路径 [4,2,1,3] 或 [5,2,1,3] 的长度。
示例 2:
输入:root = [1,2]
输出:1
提示:
树中节点数目在范围 [1, 104] 内
-100 <= Node.val <= 100
题解:
解题思路:
思路一(递归):
1、我们可以采用和计算二叉树深度同样的思想,计算二叉树的深度是挑选左右子树中深度的最大值,而二叉树的直径是左子树的最大深度深度+右子树的最大深度。
2、复杂度分析:
① 时间复杂度:O(N),其中 N 为二叉树的节点数,即遍历一棵二叉树的时间复杂度,每个结点只被访问一次。
② 空间复杂度:O(h),其中 h 为二叉树的高度(递归需要额外的栈空间)。
本题的力扣官方题解链接(非常不错)
代码实现
代码实现(思路一(递归)):
//二叉树的直径
int diameterOfBinaryTree(TreeNode* root) {depth(root);return ans;
}int depth(TreeNode *root){if(root==nullptr) return 0;//left:左子树的高度(高度指从叶结点开始测量)int left=depth(root->left);//right:右子树的高度int right=depth(root->right);//更新树的最大直径ans=max((left+right),ans);// 返回当前节点的深度return max(left,right)+1;
}
以思路一为例进行调试
#include<iostream>
#include<vector>
#include<queue>
using namespace std;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 Soluton
{int ans=0;//注意递归返回的是深度,所以我们要分成两个函数int depth(TreeNode *root){if(root==nullptr) return 0;//left:左孩子子树的高度(高度指从叶结点开始测量)int left=depth(root->left);//right:右孩子子树的高度int right=depth(root->right);//求当前两节点间的最大长度ans=max((left+right),ans);return max(left,right)+1;}public://二叉树的直径int diameterOfBinaryTree(TreeNode* root) {depth(root);return ans;}//通过数组创建二叉树(数组元素为-1代表nullptr)TreeNode *creatTree(vector<int> nums){if(nums.empty()) return nullptr;TreeNode *root=new TreeNode(nums[0]);queue<TreeNode *> q;q.push(root);int i=1;while (i<nums.size()){TreeNode *node=q.front();q.pop();if(i<nums.size()&&nums[i]!=-1){node->left=new TreeNode(nums[i]);q.push(node->left);}++i;if(i<nums.size()&&nums[i]!=-1){node->right=new TreeNode(nums[i]);q.push(node->right);}++i;}return root;}//中序遍历输出二叉树(用于调试二叉树创建是否正确)void inorder(TreeNode *root){if(root==nullptr) return ;inorder(root->left);cout<<root->val<<" ";inorder(root->right);}
};int main(){vector<int> nums={1,2,3,4,5};Soluton s;//创建二叉树TreeNode *root=s.creatTree(nums);//调试二叉树是否创建正确//s.inorder(root); cout<<"二叉树的直径:"<<s.diameterOfBinaryTree(root);return 0;
}
LeetCode 热题 100_二叉树的直径(40_543)原题链接
欢迎大家和我沟通交流(✿◠‿◠)
相关文章:
LeetCode 热题 100_二叉树的直径(40_543_简单_C++)(二叉树;递归)
LeetCode 热题 100_二叉树的直径(40_543) 题目描述:输入输出样例:题解:解题思路:思路一(递归): 代码实现代码实现(思路一(递归)&#…...
【数据结构】线性数据结构——链表
1. 定义 链表是一种线性数据结构,由多个节点(Node)组成。每个节点存储数据和指向下一个节点的指针。与数组不同,链表的节点不需要在内存中连续存储。 2. 特点 动态存储: 链表的大小不固定,可以动态增加或…...
开源存储详解-分布式存储与ceph
ceph体系结构 rados:reliable, autonomous, distributed object storage, rados rados采用c开发 对象存储 ceph严格意义讲只提供对象存储能力,ceph的块存储能力实际是基于对象存储库librados的rbd 对象存储特点 对象存储采用put/get/delete…...
[算法] [leetcode-509] 斐波那契数
509 斐波那契数 斐波那契数 (通常用 F(n) 表示)形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始,后面的每一项数字都是前面两项数字的和。也就是: F(0) 0,F(1) 1 F(n) F(n - 1) F(n - 2),其中 n…...
运维人员的Go语言学习路线
以下是一份更为详细的适合运维人员的Go语言学习路线图: 一、基础环境搭建与入门(第 1 - 2 周) 第 1 周 环境搭建 在本地开发机和常用的运维服务器环境(如 Linux 系统)中安装 Go 语言。从官方网站(https://…...
[创业之路-222]:波士顿矩阵与GE矩阵在业务组合选中作用、优缺点比较
目录 一、波士顿矩阵 1、基本原理 2、各象限产品的定义及战略对策 3、应用 4、优点与局限性 二、技术成熟度模型与产品生命周期模型的配对 1、技术成熟度模型 2、产品生命周期模型 3、技术成熟度模型与产品生命周期模型的配对 三、产品生命周期与产品类型的对应关系 …...
安卓入门十一 常用网络协议四
MQTT(Message Queuing Telemetry Transport) MQTT是一种轻量级的、发布/订阅模式的消息传输协议。它被设计用于在低带宽或不稳定网络环境下,实现物联网设备之间的可靠通信。 4.1 MQTT详细介绍 发布/订阅模式:MQTT 使用发布/订…...
《机器学习》——利用OpenCV库中的KNN算法进行图像识别
文章目录 KNN算法介绍下载OpenCV库实验内容实验结果完整代码手写数字传入模型训练 KNN算法介绍 一、KNN算法的基本要素 K值的选择:K值代表选择与新测试样本距离最近的前K个训练样本数,通常K是不大于20的整数。K值的选择对算法结果有重要影响,…...
StarRocks 存算分离在得物的降本增效实践
编者荐语: 得物优化数据引擎布局,近期将 4000 核 ClickHouse 迁移至自建 StarRocks,成本降低 40%,查询耗时减半,集群稳定性显著提升。本文详解迁移实践与成果,文末附丁凯剑老师 StarRocks Summit Asia 2024…...
Tube Qualify弯管测量系统在汽车管路三维检测中的应用
从使用量上来说,汽车行业是使用弯管零件数量最大的单一行业。在汽车的燃油,空调,排气,转向,制动等系统中都少不了管路。汽车管件形状复杂,且由于安装空间限制,汽车管件拥有不同弯曲半径…...
udp分片报文发送和接收
读文件通过udp分片发送的目的端:(包含错误的分片包) #!/usr/bin/python # -*- coding: utf-8 -*-#python send_100frag_file.py -p 55432 -f snatdownloadimport argparse import loggingfrom scapy.all import *# Define the maximum size …...
【从零开始入门unity游戏开发之——C#篇39】C#反射使用——Type 类、Assembly 类、Activator 类操作程序集
文章目录 前言一、前置知识1、编译器2、程序集(Assembly)3、元数据(Metadata) 二、反射1、反射的概念2、反射的作用3、反射的核心Type 类3.1 Type 类介绍3.2 不同方法获取 Type3.3 获取type类型所在的程序集的相关信息 4、反射的常…...
安卓触摸事件的传递
setOnTouchListener()返回值的副作用(触摸事件是否继续往下或往后传递)如下: 返回值效果是否往下层view传递是否往当前view的后续监听传递true该pointer离开屏幕前的后续所有触摸事件都会传递给该TouchListener否否false该pointer离开屏幕前…...
idea项目导入gitee 码云
1、安装gitee插件 IDEA 码云插件已由 gitosc 更名为 gitee。 1 在码云平台帮助文档http://git.mydoc.io/?t153739上介绍的很清楚,推荐前两种方法, 搜索码云插件的时候记得名字是gitee,gitosc已经搜不到了。 2、使用码云托管项目 如果之…...
典型常见的基于知识蒸馏的目标检测方法总结三
来源:Google学术2023-2024的顶会顶刊论文 NeurIPS 2022:Towards Efficient 3D Object Detection with Knowledge Distillation 为3D目标检测提出了一种知识蒸馏的Benchmark范式,包含feature的KD,Logit的cls和reg的KD,…...
端口被占用
端口8080被占用 哈哈哈,我是因为后端项目跑错了,两个项目后端名称太像了; (1)netstat -aon | findstr 8080,找到占用8080端口的进程号,获取对应的进程号pid; (2&#…...
Javascript知识框架图(待完善)
以下是一个清晰且详细的 JavaScript 知识框架,涵盖基础知识到高级概念,适合学习和参考: JavaScript 知识框架 1. 基础知识 数据类型 原始类型:Number,String,Boolean,Null,Undefin…...
清华大学Python包镜像站点
清华大学提供了一个Python包镜像站点,其中包括了许多常用的Python包。使用这个镜像站点可以提高下载Python包时的速度,因为包已经存储在国内的服务器上,从而减少了网络延迟。 要使用清华的pip镜像,你可以在pip命令中指定-i参数来…...
逆境清醒文章总目录表
逆境清醒文章总目录表 零、时光宝盒🌻 (https://blog.csdn.net/weixin_69553582 逆境清醒) 《你的答案》歌曲原唱:阿冗,填 词:林晨阳、刘涛,谱曲:刘涛 也许世界就这样,…...
LeetCode算法题——移除元素
题目描述 给你一个数组 nums 和一个值 val,你需要原地移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。 假设 nums 中不等于 val 的元素数量为 k,要通过此题,您需要执行以下操作࿱…...
React 第五十五节 Router 中 useAsyncError的使用详解
前言 useAsyncError 是 React Router v6.4 引入的一个钩子,用于处理异步操作(如数据加载)中的错误。下面我将详细解释其用途并提供代码示例。 一、useAsyncError 用途 处理异步错误:捕获在 loader 或 action 中发生的异步错误替…...
DeepSeek 赋能智慧能源:微电网优化调度的智能革新路径
目录 一、智慧能源微电网优化调度概述1.1 智慧能源微电网概念1.2 优化调度的重要性1.3 目前面临的挑战 二、DeepSeek 技术探秘2.1 DeepSeek 技术原理2.2 DeepSeek 独特优势2.3 DeepSeek 在 AI 领域地位 三、DeepSeek 在微电网优化调度中的应用剖析3.1 数据处理与分析3.2 预测与…...
Java如何权衡是使用无序的数组还是有序的数组
在 Java 中,选择有序数组还是无序数组取决于具体场景的性能需求与操作特点。以下是关键权衡因素及决策指南: ⚖️ 核心权衡维度 维度有序数组无序数组查询性能二分查找 O(log n) ✅线性扫描 O(n) ❌插入/删除需移位维护顺序 O(n) ❌直接操作尾部 O(1) ✅内存开销与无序数组相…...
Qwen3-Embedding-0.6B深度解析:多语言语义检索的轻量级利器
第一章 引言:语义表示的新时代挑战与Qwen3的破局之路 1.1 文本嵌入的核心价值与技术演进 在人工智能领域,文本嵌入技术如同连接自然语言与机器理解的“神经突触”——它将人类语言转化为计算机可计算的语义向量,支撑着搜索引擎、推荐系统、…...
LLM基础1_语言模型如何处理文本
基于GitHub项目:https://github.com/datawhalechina/llms-from-scratch-cn 工具介绍 tiktoken:OpenAI开发的专业"分词器" torch:Facebook开发的强力计算引擎,相当于超级计算器 理解词嵌入:给词语画"…...
Python基于历史模拟方法实现投资组合风险管理的VaR与ES模型项目实战
说明:这是一个机器学习实战项目(附带数据代码文档),如需数据代码文档可以直接到文章最后关注获取。 1.项目背景 在金融市场日益复杂和波动加剧的背景下,风险管理成为金融机构和个人投资者关注的核心议题之一。VaR&…...
Git常用命令完全指南:从入门到精通
Git常用命令完全指南:从入门到精通 一、基础配置命令 1. 用户信息配置 # 设置全局用户名 git config --global user.name "你的名字"# 设置全局邮箱 git config --global user.email "你的邮箱example.com"# 查看所有配置 git config --list…...
相关类相关的可视化图像总结
目录 一、散点图 二、气泡图 三、相关图 四、热力图 五、二维密度图 六、多模态二维密度图 七、雷达图 八、桑基图 九、总结 一、散点图 特点 通过点的位置展示两个连续变量之间的关系,可直观判断线性相关、非线性相关或无相关关系,点的分布密…...
STM32标准库-ADC数模转换器
文章目录 一、ADC1.1简介1. 2逐次逼近型ADC1.3ADC框图1.4ADC基本结构1.4.1 信号 “上车点”:输入模块(GPIO、温度、V_REFINT)1.4.2 信号 “调度站”:多路开关1.4.3 信号 “加工厂”:ADC 转换器(规则组 注入…...
13.10 LangGraph多轮对话系统实战:Ollama私有部署+情感识别优化全解析
LangGraph多轮对话系统实战:Ollama私有部署+情感识别优化全解析 LanguageMentor 对话式训练系统架构与实现 关键词:多轮对话系统设计、场景化提示工程、情感识别优化、LangGraph 状态管理、Ollama 私有化部署 1. 对话训练系统技术架构 采用四层架构实现高扩展性的对话训练…...
