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

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_二叉树的直径&#xff08;40_543&#xff09; 题目描述&#xff1a;输入输出样例&#xff1a;题解&#xff1a;解题思路&#xff1a;思路一&#xff08;递归&#xff09;&#xff1a; 代码实现代码实现&#xff08;思路一&#xff08;递归&#xff09;&#…...

【数据结构】线性数据结构——链表

1. 定义 链表是一种线性数据结构&#xff0c;由多个节点&#xff08;Node&#xff09;组成。每个节点存储数据和指向下一个节点的指针。与数组不同&#xff0c;链表的节点不需要在内存中连续存储。 2. 特点 动态存储&#xff1a; 链表的大小不固定&#xff0c;可以动态增加或…...

开源存储详解-分布式存储与ceph

ceph体系结构 rados&#xff1a;reliable, autonomous, distributed object storage, rados rados采用c开发 对象存储 ceph严格意义讲只提供对象存储能力&#xff0c;ceph的块存储能力实际是基于对象存储库librados的rbd 对象存储特点 对象存储采用put/get/delete&#xf…...

[算法] [leetcode-509] 斐波那契数

509 斐波那契数 斐波那契数 &#xff08;通常用 F(n) 表示&#xff09;形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始&#xff0c;后面的每一项数字都是前面两项数字的和。也就是&#xff1a; F(0) 0&#xff0c;F(1) 1 F(n) F(n - 1) F(n - 2)&#xff0c;其中 n…...

运维人员的Go语言学习路线

以下是一份更为详细的适合运维人员的Go语言学习路线图&#xff1a; 一、基础环境搭建与入门&#xff08;第 1 - 2 周&#xff09; 第 1 周 环境搭建 在本地开发机和常用的运维服务器环境&#xff08;如 Linux 系统&#xff09;中安装 Go 语言。从官方网站&#xff08;https://…...

[创业之路-222]:波士顿矩阵与GE矩阵在业务组合选中作用、优缺点比较

目录 一、波士顿矩阵 1、基本原理 2、各象限产品的定义及战略对策 3、应用 4、优点与局限性 二、技术成熟度模型与产品生命周期模型的配对 1、技术成熟度模型 2、产品生命周期模型 3、技术成熟度模型与产品生命周期模型的配对 三、产品生命周期与产品类型的对应关系 …...

安卓入门十一 常用网络协议四

MQTT&#xff08;Message Queuing Telemetry Transport&#xff09; MQTT是一种轻量级的、发布/订阅模式的消息传输协议。它被设计用于在低带宽或不稳定网络环境下&#xff0c;实现物联网设备之间的可靠通信。 4.1 MQTT详细介绍 发布/订阅模式&#xff1a;MQTT 使用发布/订…...

《机器学习》——利用OpenCV库中的KNN算法进行图像识别

文章目录 KNN算法介绍下载OpenCV库实验内容实验结果完整代码手写数字传入模型训练 KNN算法介绍 一、KNN算法的基本要素 K值的选择&#xff1a;K值代表选择与新测试样本距离最近的前K个训练样本数&#xff0c;通常K是不大于20的整数。K值的选择对算法结果有重要影响&#xff0c…...

StarRocks 存算分离在得物的降本增效实践

编者荐语&#xff1a; 得物优化数据引擎布局&#xff0c;近期将 4000 核 ClickHouse 迁移至自建 StarRocks&#xff0c;成本降低 40%&#xff0c;查询耗时减半&#xff0c;集群稳定性显著提升。本文详解迁移实践与成果&#xff0c;文末附丁凯剑老师 StarRocks Summit Asia 2024…...

Tube Qualify弯管测量系统在汽车管路三维检测中的应用

从使用量上来说&#xff0c;汽车行业是使用弯管零件数量最大的单一行业。在汽车的燃油&#xff0c;空调&#xff0c;排气&#xff0c;转向&#xff0c;制动等系统中都少不了管路。汽车管件形状复杂&#xff0c;且由于安装空间限制&#xff0c;汽车管件拥有不同弯曲半径&#xf…...

udp分片报文发送和接收

读文件通过udp分片发送的目的端&#xff1a;&#xff08;包含错误的分片包&#xff09; #!/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、程序集&#xff08;Assembly&#xff09;3、元数据&#xff08;Metadata&#xff09; 二、反射1、反射的概念2、反射的作用3、反射的核心Type 类3.1 Type 类介绍3.2 不同方法获取 Type3.3 获取type类型所在的程序集的相关信息 4、反射的常…...

安卓触摸事件的传递

setOnTouchListener()返回值的副作用&#xff08;触摸事件是否继续往下或往后传递&#xff09;如下&#xff1a; 返回值效果是否往下层view传递是否往当前view的后续监听传递true该pointer离开屏幕前的后续所有触摸事件都会传递给该TouchListener否否false该pointer离开屏幕前…...

idea项目导入gitee 码云

1、安装gitee插件 IDEA 码云插件已由 gitosc 更名为 gitee。 1 在码云平台帮助文档http://git.mydoc.io/?t153739上介绍的很清楚&#xff0c;推荐前两种方法&#xff0c; 搜索码云插件的时候记得名字是gitee&#xff0c;gitosc已经搜不到了。 2、使用码云托管项目 如果之…...

典型常见的基于知识蒸馏的目标检测方法总结三

来源&#xff1a;Google学术2023-2024的顶会顶刊论文 NeurIPS 2022&#xff1a;Towards Efficient 3D Object Detection with Knowledge Distillation 为3D目标检测提出了一种知识蒸馏的Benchmark范式&#xff0c;包含feature的KD&#xff0c;Logit的cls和reg的KD&#xff0c…...

端口被占用

端口8080被占用 哈哈哈&#xff0c;我是因为后端项目跑错了&#xff0c;两个项目后端名称太像了&#xff1b; &#xff08;1&#xff09;netstat -aon | findstr 8080&#xff0c;找到占用8080端口的进程号&#xff0c;获取对应的进程号pid&#xff1b; &#xff08;2&#…...

Javascript知识框架图(待完善)

以下是一个清晰且详细的 JavaScript 知识框架&#xff0c;涵盖基础知识到高级概念&#xff0c;适合学习和参考&#xff1a; JavaScript 知识框架 1. 基础知识 数据类型 原始类型&#xff1a;Number&#xff0c;String&#xff0c;Boolean&#xff0c;Null&#xff0c;Undefin…...

清华大学Python包镜像站点

清华大学提供了一个Python包镜像站点&#xff0c;其中包括了许多常用的Python包。使用这个镜像站点可以提高下载Python包时的速度&#xff0c;因为包已经存储在国内的服务器上&#xff0c;从而减少了网络延迟。 要使用清华的pip镜像&#xff0c;你可以在pip命令中指定-i参数来…...

逆境清醒文章总目录表

逆境清醒文章总目录表 零、时光宝盒&#x1f33b; &#xff08;https://blog.csdn.net/weixin_69553582 逆境清醒&#xff09; 《你的答案》歌曲原唱&#xff1a;阿冗&#xff0c;填 词&#xff1a;林晨阳、刘涛&#xff0c;谱曲&#xff1a;刘涛 也许世界就这样&#xff0c…...

LeetCode算法题——移除元素

题目描述 给你一个数组 nums 和一个值 val&#xff0c;你需要原地移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。 假设 nums 中不等于 val 的元素数量为 k&#xff0c;要通过此题&#xff0c;您需要执行以下操作&#xff1…...

day52 ResNet18 CBAM

在深度学习的旅程中&#xff0c;我们不断探索如何提升模型的性能。今天&#xff0c;我将分享我在 ResNet18 模型中插入 CBAM&#xff08;Convolutional Block Attention Module&#xff09;模块&#xff0c;并采用分阶段微调策略的实践过程。通过这个过程&#xff0c;我不仅提升…...

【OSG学习笔记】Day 16: 骨骼动画与蒙皮(osgAnimation)

骨骼动画基础 骨骼动画是 3D 计算机图形中常用的技术&#xff0c;它通过以下两个主要组件实现角色动画。 骨骼系统 (Skeleton)&#xff1a;由层级结构的骨头组成&#xff0c;类似于人体骨骼蒙皮 (Mesh Skinning)&#xff1a;将模型网格顶点绑定到骨骼上&#xff0c;使骨骼移动…...

根据万维钢·精英日课6的内容,使用AI(2025)可以参考以下方法:

根据万维钢精英日课6的内容&#xff0c;使用AI&#xff08;2025&#xff09;可以参考以下方法&#xff1a; 四个洞见 模型已经比人聪明&#xff1a;以ChatGPT o3为代表的AI非常强大&#xff0c;能运用高级理论解释道理、引用最新学术论文&#xff0c;生成对顶尖科学家都有用的…...

laravel8+vue3.0+element-plus搭建方法

创建 laravel8 项目 composer create-project --prefer-dist laravel/laravel laravel8 8.* 安装 laravel/ui composer require laravel/ui 修改 package.json 文件 "devDependencies": {"vue/compiler-sfc": "^3.0.7","axios": …...

七、数据库的完整性

七、数据库的完整性 主要内容 7.1 数据库的完整性概述 7.2 实体完整性 7.3 参照完整性 7.4 用户定义的完整性 7.5 触发器 7.6 SQL Server中数据库完整性的实现 7.7 小结 7.1 数据库的完整性概述 数据库完整性的含义 正确性 指数据的合法性 有效性 指数据是否属于所定…...

如何更改默认 Crontab 编辑器 ?

在 Linux 领域中&#xff0c;crontab 是您可能经常遇到的一个术语。这个实用程序在类 unix 操作系统上可用&#xff0c;用于调度在预定义时间和间隔自动执行的任务。这对管理员和高级用户非常有益&#xff0c;允许他们自动执行各种系统任务。 编辑 Crontab 文件通常使用文本编…...

2025年渗透测试面试题总结-腾讯[实习]科恩实验室-安全工程师(题目+回答)

安全领域各种资源&#xff0c;学习文档&#xff0c;以及工具分享、前沿信息分享、POC、EXP分享。不定期分享各种好玩的项目及好用的工具&#xff0c;欢迎关注。 目录 腾讯[实习]科恩实验室-安全工程师 一、网络与协议 1. TCP三次握手 2. SYN扫描原理 3. HTTPS证书机制 二…...

Redis:现代应用开发的高效内存数据存储利器

一、Redis的起源与发展 Redis最初由意大利程序员Salvatore Sanfilippo在2009年开发&#xff0c;其初衷是为了满足他自己的一个项目需求&#xff0c;即需要一个高性能的键值存储系统来解决传统数据库在高并发场景下的性能瓶颈。随着项目的开源&#xff0c;Redis凭借其简单易用、…...

【Linux】自动化构建-Make/Makefile

前言 上文我们讲到了Linux中的编译器gcc/g 【Linux】编译器gcc/g及其库的详细介绍-CSDN博客 本来我们将一个对于编译来说很重要的工具&#xff1a;make/makfile 1.背景 在一个工程中源文件不计其数&#xff0c;其按类型、功能、模块分别放在若干个目录中&#xff0c;mak…...

Linux部署私有文件管理系统MinIO

最近需要用到一个文件管理服务&#xff0c;但是又不想花钱&#xff0c;所以就想着自己搭建一个&#xff0c;刚好我们用的一个开源框架已经集成了MinIO&#xff0c;所以就选了这个 我这边对文件服务性能要求不是太高&#xff0c;单机版就可以 安装非常简单&#xff0c;几个命令就…...