当前位置: 首页 > 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…...

uni-app学习笔记二十二---使用vite.config.js全局导入常用依赖

在前面的练习中&#xff0c;每个页面需要使用ref&#xff0c;onShow等生命周期钩子函数时都需要像下面这样导入 import {onMounted, ref} from "vue" 如果不想每个页面都导入&#xff0c;需要使用node.js命令npm安装unplugin-auto-import npm install unplugin-au…...

高频面试之3Zookeeper

高频面试之3Zookeeper 文章目录 高频面试之3Zookeeper3.1 常用命令3.2 选举机制3.3 Zookeeper符合法则中哪两个&#xff1f;3.4 Zookeeper脑裂3.5 Zookeeper用来干嘛了 3.1 常用命令 ls、get、create、delete、deleteall3.2 选举机制 半数机制&#xff08;过半机制&#xff0…...

MVC 数据库

MVC 数据库 引言 在软件开发领域,Model-View-Controller(MVC)是一种流行的软件架构模式,它将应用程序分为三个核心组件:模型(Model)、视图(View)和控制器(Controller)。这种模式有助于提高代码的可维护性和可扩展性。本文将深入探讨MVC架构与数据库之间的关系,以…...

在Ubuntu中设置开机自动运行(sudo)指令的指南

在Ubuntu系统中&#xff0c;有时需要在系统启动时自动执行某些命令&#xff0c;特别是需要 sudo权限的指令。为了实现这一功能&#xff0c;可以使用多种方法&#xff0c;包括编写Systemd服务、配置 rc.local文件或使用 cron任务计划。本文将详细介绍这些方法&#xff0c;并提供…...

CocosCreator 之 JavaScript/TypeScript和Java的相互交互

引擎版本&#xff1a; 3.8.1 语言&#xff1a; JavaScript/TypeScript、C、Java 环境&#xff1a;Window 参考&#xff1a;Java原生反射机制 您好&#xff0c;我是鹤九日&#xff01; 回顾 在上篇文章中&#xff1a;CocosCreator Android项目接入UnityAds 广告SDK。 我们简单讲…...

Ascend NPU上适配Step-Audio模型

1 概述 1.1 简述 Step-Audio 是业界首个集语音理解与生成控制一体化的产品级开源实时语音对话系统&#xff0c;支持多语言对话&#xff08;如 中文&#xff0c;英文&#xff0c;日语&#xff09;&#xff0c;语音情感&#xff08;如 开心&#xff0c;悲伤&#xff09;&#x…...

AI书签管理工具开发全记录(十九):嵌入资源处理

1.前言 &#x1f4dd; 在上一篇文章中&#xff0c;我们完成了书签的导入导出功能。本篇文章我们研究如何处理嵌入资源&#xff0c;方便后续将资源打包到一个可执行文件中。 2.embed介绍 &#x1f3af; Go 1.16 引入了革命性的 embed 包&#xff0c;彻底改变了静态资源管理的…...

稳定币的深度剖析与展望

一、引言 在当今数字化浪潮席卷全球的时代&#xff0c;加密货币作为一种新兴的金融现象&#xff0c;正以前所未有的速度改变着我们对传统货币和金融体系的认知。然而&#xff0c;加密货币市场的高度波动性却成为了其广泛应用和普及的一大障碍。在这样的背景下&#xff0c;稳定…...

JVM 内存结构 详解

内存结构 运行时数据区&#xff1a; Java虚拟机在运行Java程序过程中管理的内存区域。 程序计数器&#xff1a; ​ 线程私有&#xff0c;程序控制流的指示器&#xff0c;分支、循环、跳转、异常处理、线程恢复等基础功能都依赖这个计数器完成。 ​ 每个线程都有一个程序计数…...

【VLNs篇】07:NavRL—在动态环境中学习安全飞行

项目内容论文标题NavRL: 在动态环境中学习安全飞行 (NavRL: Learning Safe Flight in Dynamic Environments)核心问题解决无人机在包含静态和动态障碍物的复杂环境中进行安全、高效自主导航的挑战&#xff0c;克服传统方法和现有强化学习方法的局限性。核心算法基于近端策略优化…...