二叉树题目:二叉树的直径
文章目录
- 题目
- 标题和出处
- 难度
- 题目描述
- 要求
- 示例
- 数据范围
- 解法
- 思路和算法
- 代码
- 复杂度分析
题目
标题和出处
标题:二叉树的直径
出处:543. 二叉树的直径
难度
3 级
题目描述
要求
给定二叉树的根结点 root \texttt{root} root,返回其直径长度。
二叉树的直径是任意两个结点之间的最长路径长度。这条路径可能穿过也可能不穿过根结点。
两个结点之间的路径长度由它们之间边的数目表示。
示例
示例 1:

输入: root = [1,2,3,4,5] \texttt{root = [1,2,3,4,5]} root = [1,2,3,4,5]
输出: 3 \texttt{3} 3
解释: 3 \texttt{3} 3 是路径 [4,2,1,3] \texttt{[4,2,1,3]} [4,2,1,3] 或 [5,2,1,3] \texttt{[5,2,1,3]} [5,2,1,3] 的长度。
示例 2:
输入: root = [1,2] \texttt{root = [1,2]} root = [1,2]
输出: 1 \texttt{1} 1
数据范围
- 树中结点数目在范围 [1, 10 4 ] \texttt{[1, 10}^\texttt{4}\texttt{]} [1, 104] 内
- -100 ≤ Node.val ≤ 100 \texttt{-100} \le \texttt{Node.val} \le \texttt{100} -100≤Node.val≤100
解法
思路和算法
二叉树中的任意一条路径一定经过某个子树的根结点,子树可以是二叉树本身。
对于任意一个子树而言,经过该子树根结点的最长路径(以下称为「最长路径」,均指包含根结点的最长路径)一定满足以下条件:如果左子树不为空,则最长路径的左端是左子树的最深叶结点,否则最长路径的左端是根结点;如果右子树不为空,则最长路径的右端是右子树的最深叶结点,否则最长路径的右端是根结点。因此,子树的最长路径长度为该子树的左子树和右子树的深度之和,子树的深度为该子树的左子树和右子树的深度的较大值加 1 1 1。此处的深度定义为二叉树中结点的层数,如果二叉树为空则深度为 0 0 0,如果二叉树只有一个结点则深度为 1 1 1。
由于二叉树的最长路径长度和二叉树的深度都取决于左子树和右子树的深度,因此可以使用深度优先搜索计算二叉树的深度,计算过程中得到二叉树的直径。
计算二叉树的深度的过程是一个递归的过程,递归的终止条件是当前结点为空,此时深度为 0 0 0。其余情况下,首先得到当前结点的左子树和右子树的深度,然后计算以当前结点为根结点的二叉树的深度和最长路径长度,并维护二叉树的直径。遍历结束之后,即可得到二叉树的直径。
代码
class Solution {int diameter = 0;public int diameterOfBinaryTree(TreeNode root) {getDepth(root);return diameter;}public int getDepth(TreeNode node) {if (node == null) {return 0;}int leftDepth = getDepth(node.left);int rightDepth = getDepth(node.right);diameter = Math.max(diameter, leftDepth + rightDepth);return Math.max(leftDepth, rightDepth) + 1;}
}
复杂度分析
-
时间复杂度: O ( n ) O(n) O(n),其中 n n n 是二叉树的结点数。每个结点都被访问一次。
-
空间复杂度: O ( n ) O(n) O(n),其中 n n n 是二叉树的结点数。空间复杂度主要是递归调用的栈空间,取决于二叉树的高度,最坏情况下是 O ( n ) O(n) O(n)。
相关文章:
二叉树题目:二叉树的直径
文章目录 题目标题和出处难度题目描述要求示例数据范围 解法思路和算法代码复杂度分析 题目 标题和出处 标题:二叉树的直径 出处:543. 二叉树的直径 难度 3 级 题目描述 要求 给定二叉树的根结点 root \texttt{root} root,返回其直径…...
嵌入式:C高级 Day4
一、整理思维导图 二、写一个函数,获取用户的uid和gid并使用变量接收 三、整理冒泡排序、简单选择排序和快速排序的代码 冒泡排序 #include <myhead.h>void output(int arr[], int len); void bubble_sort(int arr[], int len);int main(int argc, const ch…...
cmake常用命令(1)——函数相关
一、function/endfunction cmake中的函数与其他语言相似,表示一个命令集,可以被重复调用。形式如下: function(<name> [<arg1> ...])<commands> endfunction() function:表示函数开始 <name>…...
阿里三年功能测试的一些感悟
一、前言 功能测试是测试工程师的基础功,很多人功能测试还做不好,就想去做性能测试、自动化测试。很多人对功能测试的理解就是点点点,如何自己不用心去悟,去研究,那么你的职业生涯也就停留在点点点上了。在这里&#…...
React源码解析18(4)------ completeWork的工作流程【mount】
摘要 经过上一章,我们得到的FilberNode已经具有了child和return属性。一颗Filber树的结构已经展现出来了。 那我们最终是想在页面渲染真实的DOM。所以我们现在要在completeWork里,构建出一颗离屏的DOM树。 之前在说FilberNode的属性时,我们…...
Kafka: 详解、使用教程和示例
Kafka: 详细介绍、使用教程和示例 什么是 Kafka? Kafka 是一个分布式的流处理平台,最初由 LinkedIn 开发,现已成为 Apache 基金会的顶级项目。它以高吞吐量、可靠性和可扩展性而闻名,被广泛应用于实时数据传输、日志收集、事件处…...
【LeetCode周赛】LeetCode第358场周赛
LeetCode第358场周赛 数组中的最大数对和翻倍以链表形式表示的数字限制条件下元素之间的最小绝对差 数组中的最大数对和 给你一个下标从0开始的整数数组nums。请你从nums中找出和最大的一对数,且这两个数数位上最大的数字相等。 返回最大和,如果不存在满…...
Node.js学习笔记-04
这第九章也是个大重点 九、玩转进程 Node在选型时决定在V8引擎之上构建,也就意味着它的模型与浏览器类似。 本章关于进程的介绍和讨论将会解决如下两个问题: 单进程单线程并非完美,如今CPU基本均是多核的,真正的服务器…...
基于dbn+svr的交通流量预测,dbn详细原理
目录 背影 DBN神经网络的原理 DBN神经网络的定义 受限玻尔兹曼机(RBM) DBN+SVR的交通流量预测 基本结构 主要参数 数据 MATALB代码 结果图 展望 背影 DBN是一种深度学习神经网络,拥有提取特征,非监督学习的能力,是一种非常好的分类算法,本文将DBN+SVR用于交通流量预测…...
【第一阶段】kotlin中反引号中的函数名特点
在kotlin中可以直接中文定义函数,使用反引号进行调用 eg: fun main() {2023年8月9日定义的函数(5) }private fun 2023年8月9日定义的函数(num:Int){println("反引号的用法$num") }执行结果 在Java中is,in可以定义方法,但是在kotlin中is,in是…...
数据分析-python学习 (1)numpy相关
内容为:https://juejin.cn/book/7240731597035864121的学习笔记 导包 import numpy as np numpy数组创建 创建全0数组,正态分布、随机数组等就不说了,提供了相应的方法通过已有数据创建有两种 arr1np.array([1,2,3,4,5]) 或者datanp.loadt…...
数据库的游标
数据库的游标(Cursor)是用于在数据库中进行数据操作的一个控制结构。它类似于在编程语言中使用的指针或迭代器,用于遍历数据库结果集并在结果集上执行各种操作。 游标允许我们在数据库查询的结果集中逐行移动,并对每一行执行特定…...
【设计模式】前端控制器模式
前端控制器模式(Front Controller Pattern)是用来提供一个集中的请求处理机制,所有的请求都将由一个单一的处理程序处理。该处理程序可以做认证/授权/记录日志,或者跟踪请求,然后把请求传给相应的处理程序。以下是这种…...
SQL | 过滤数据
4-过滤数据 4.1-使用WHERE子句 数据根据 WHERE 子句中指定的搜索条件进行过滤。WHERE 子句在表名( FROM 子句)之后给出。 select prod_name,prod_price from products where prod_price 3.49; 上述语句查询价格为3.49的行,然后输出名字和…...
【力扣每日一题】2023.8.13 合并两个有序数组
目录 题目: 示例: 分析: 代码: 题目: 示例: 分析: 题目给我们两个升序数组,让我们合并它们,要求合并之后仍然是升序,并且这个合并操作是在数组1原地修改…...
数据结构篇七:排序
文章目录 前言1.插入排序1.1 基本思想1.2 代码实现1.3 特性总结 2.希尔排序2.1 基本思想2.2 代码实现2.3 特性总结 3. 选择排序3.1 基本思想3.2 代码实现3.3 特性总结 4. 堆排序4.1 基本思想4.2 代码实现4.3 特性总结 5. 冒泡排序5.1 基本思想5.2 代码实现5.3 特性总结 6. 快速…...
Vue组件的边界情况
01.$root; 访问组件的根实例;用的不多,基本上在vuex上进行数据操作; 02.$parent/$children; 可以获得父组件或者子组件上边的数据;一般不建议使用$parent,因为如果获取这个值进行修改的话,也会更改父组件上…...
less、sass的使用及其区别
CSS预处理器 CSS 预处理器是一种扩展了原生 CSS 的工具,它们添加了一些编程语言的特性,以便更有效地编写、组织和维护样式代码。预处理器允许开发者使用变量、嵌套、函数、混合等功能,从而使 CSS 更具可读性、可维护性和重用性,特…...
[保研/考研机试] 猫狗收容所 C++实现
题目描述: 输入: 第一个是n,它代表操作序列的次数。接下来是n行,每行有两个值m和t,分别代表题目中操作的两个元素。 输出: 按顺序输出收养动物的序列,编号之间以空格间隔。 源代码ÿ…...
Kotlin 基础教程一
Kotlin 基本数据类型 Java | Kotlin byte Byte short Short int Int long Long float Float double Double boolean Boolean c…...
python打卡day49
知识点回顾: 通道注意力模块复习空间注意力模块CBAM的定义 作业:尝试对今天的模型检查参数数目,并用tensorboard查看训练过程 import torch import torch.nn as nn# 定义通道注意力 class ChannelAttention(nn.Module):def __init__(self,…...
蓝桥杯 2024 15届国赛 A组 儿童节快乐
P10576 [蓝桥杯 2024 国 A] 儿童节快乐 题目描述 五彩斑斓的气球在蓝天下悠然飘荡,轻快的音乐在耳边持续回荡,小朋友们手牵着手一同畅快欢笑。在这样一片安乐祥和的氛围下,六一来了。 今天是六一儿童节,小蓝老师为了让大家在节…...
linux 错误码总结
1,错误码的概念与作用 在Linux系统中,错误码是系统调用或库函数在执行失败时返回的特定数值,用于指示具体的错误类型。这些错误码通过全局变量errno来存储和传递,errno由操作系统维护,保存最近一次发生的错误信息。值得注意的是,errno的值在每次系统调用或函数调用失败时…...
OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别
OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别 直接训练提示词嵌入向量的核心区别 您提到的代码: prompt_embedding = initial_embedding.clone().requires_grad_(True) optimizer = torch.optim.Adam([prompt_embedding...
DeepSeek 技术赋能无人农场协同作业:用 AI 重构农田管理 “神经网”
目录 一、引言二、DeepSeek 技术大揭秘2.1 核心架构解析2.2 关键技术剖析 三、智能农业无人农场协同作业现状3.1 发展现状概述3.2 协同作业模式介绍 四、DeepSeek 的 “农场奇妙游”4.1 数据处理与分析4.2 作物生长监测与预测4.3 病虫害防治4.4 农机协同作业调度 五、实际案例大…...
JS手写代码篇----使用Promise封装AJAX请求
15、使用Promise封装AJAX请求 promise就有reject和resolve了,就不必写成功和失败的回调函数了 const BASEURL ./手写ajax/test.jsonfunction promiseAjax() {return new Promise((resolve, reject) > {const xhr new XMLHttpRequest();xhr.open("get&quo…...
【Elasticsearch】Elasticsearch 在大数据生态圈的地位 实践经验
Elasticsearch 在大数据生态圈的地位 & 实践经验 1.Elasticsearch 的优势1.1 Elasticsearch 解决的核心问题1.1.1 传统方案的短板1.1.2 Elasticsearch 的解决方案 1.2 与大数据组件的对比优势1.3 关键优势技术支撑1.4 Elasticsearch 的竞品1.4.1 全文搜索领域1.4.2 日志分析…...
Ubuntu系统复制(U盘-电脑硬盘)
所需环境 电脑自带硬盘:1块 (1T) U盘1:Ubuntu系统引导盘(用于“U盘2”复制到“电脑自带硬盘”) U盘2:Ubuntu系统盘(1T,用于被复制) !!!建议“电脑…...
SpringAI实战:ChatModel智能对话全解
一、引言:Spring AI 与 Chat Model 的核心价值 🚀 在 Java 生态中集成大模型能力,Spring AI 提供了高效的解决方案 🤖。其中 Chat Model 作为核心交互组件,通过标准化接口简化了与大语言模型(LLM࿰…...
算法打卡第18天
从中序与后序遍历序列构造二叉树 (力扣106题) 给定两个整数数组 inorder 和 postorder ,其中 inorder 是二叉树的中序遍历, postorder 是同一棵树的后序遍历,请你构造并返回这颗 二叉树 。 示例 1: 输入:inorder [9,3,15,20,7…...
