LeetCode 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

方法一:深度优先搜索

首先我们知道一条路径的长度为该路径经过的节点数减一,所以求直径(即求路径长度的最大值)等效于求路径经过节点数的最大值减一。

而任意一条路径均可以被看作由某个节点为起点,从其左儿子和右儿子向下遍历的路径拼接得到。

在这里插入图片描述

class Solution {int ans;public int diameterOfBinaryTree(TreeNode root) {ans = 1;depth(root);return ans - 1;}public int depth(TreeNode node) {if (node == null) {return 0; // 访问到空节点了,返回0}int L = depth(node.left); // 左儿子为根的子树的深度int R = depth(node.right); // 右儿子为根的子树的深度ans = Math.max(ans, L+R+1); // 计算d_node即L+R+1 并更新ansreturn Math.max(L, R) + 1; // 返回该节点为根的子树的深度}
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/305678.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

JUC:实现一个简易的数据库连接池(享元模式)

主要是学习享元模式。 享元模式&#xff08;Flyweight Pattern&#xff09;是一种结构型设计模式&#xff0c;旨在通过共享尽可能多的对象来最小化内存使用和提高性能。在该模式中&#xff0c;对象被分为两种状态&#xff1a;内部状态和外部状态。 内部状态&#xff08;Intr…

C++ | Leetcode C++题解之第22题括号生成

题目&#xff1a; 题解&#xff1a; class Solution { public:vector<string> res; //记录答案 vector<string> generateParenthesis(int n) {dfs(n , 0 , 0, "");return res;}void dfs(int n ,int lc, int rc ,string str){if( lc n && rc n…

【星期计算】蓝桥杯

–> 因为这里是结果填空题&#xff0c;我们直接暴力用java自带的BigInteger类。 /*** 试题 A: 星期计算** 本题总分&#xff1a;5 分* 【问题描述】* 已知今天是星期六&#xff0c;请问20的22次方天后是星期几&#xff1f;* 注意用数字 1 到 7 表示星期一到星期日。* * 【答…

泽众Testone自动化测试平台,测试用例支持单个调试执行,同步查看执行日志

泽众Testone自动化测试平台之前版本&#xff0c;测试用例批量和单个执行&#xff0c;必须要通过测试集操作执行&#xff0c;操作略繁琐&#xff0c;我们通过本轮优化升级&#xff0c;测试用例直接可以单个调试执行&#xff0c;同步查看执行日志&#xff0c;操作上去繁就简&…

《云原生安全攻防》-- 云原生应用风险分析

为了满足每位朋友的学习需求&#xff0c;并且支持课程的持续更新&#xff0c;本系列课程提供了免费版和付费视频版两种方式来提供课程内容。我们会持续更新课程内容&#xff0c;以确保内容的度和实用性。 在本节课程中&#xff0c;我们将一起探讨云原生应用在新的架构模式下可能…

Linux的学习之路:5、粘滞位与vim

摘要 这里主要是把上章没说完的权限的粘滞位说一下&#xff0c;然后就是vim的一些操作。 目录 摘要 一、粘滞位 二、权限总结 三、vim的基本概念 四、vim的基本操作 五、vim正常模式命令集 1、插入模式 2、从插入模式切换为命令模式 3、移动光标 4、删除文字 5、复…

Mysql内存表及使用场景(12/16)

内存表&#xff08;Memory引擎&#xff09; InnoDB引擎使用B树作为主键索引&#xff0c;数据按照索引顺序存储&#xff0c;称为索引组织表&#xff08;Index Organized Table&#xff09;。 Memory引擎的数据和索引分开存储&#xff0c;数据以数组形式存放&#xff0c;主键索…

【数据结构】两两交换链表 复制带随机指针的链表

问题描述1 给你一个链表&#xff0c;两两交换其中相邻的节点&#xff0c;并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题&#xff08;即&#xff0c;只能进行节点交换&#xff09;。 求解 使用一个栈S来存储相邻两个节点即可 /*** Definition for…

5G-A有何能耐?5G-A三载波聚合技术介绍

2024年被称作5G-A元年。5G-A作为5G下一阶段的演进技术&#xff0c;到底有何能耐呢&#xff1f; 三载波聚合&#xff08;3CC&#xff09;被认为是首个大规模商用的5G-A技术&#xff0c;将带来手机网速的大幅提升。 █ 什么是3CC 3CC&#xff0c;全称叫3 Component Carriers…

Python 基于 OpenCV 视觉图像处理实战 之 OpenCV 简单视频处理实战案例 之九 简单视频卡通画效果

Python 基于 OpenCV 视觉图像处理实战 之 OpenCV 简单视频处理实战案例 之九 简单视频卡通画效果 目录 Python 基于 OpenCV 视觉图像处理实战 之 OpenCV 简单视频处理实战案例 之九 简单视频卡通画效果 一、简单介绍 二、简单视频卡通画效果实现原理 三、简单视频卡通画效果…

spring.rabbitmq.listener.simple.default-requeue-rejected = false 和放入死信队列的区别

目录 一、场景 二、使用 spring.rabbitmq.listener.simple.default-requeue-rejected false 2.1 特点 三、 放入死信队列 四、两种区别 一、场景 当我们使用RabbitMq的时候&#xff0c;我们如果业务中有异常&#xff0c;很有可能造成死循环&#xff0c;因为 在RabbitMQ和…

【随笔】Git 高级篇 -- 纠缠不清的分支 rebase | cherry-pick(二十四)

&#x1f48c; 所属专栏&#xff1a;【Git】 &#x1f600; 作  者&#xff1a;我是夜阑的狗&#x1f436; &#x1f680; 个人简介&#xff1a;一个正在努力学技术的CV工程师&#xff0c;专注基础和实战分享 &#xff0c;欢迎咨询&#xff01; &#x1f496; 欢迎大…

2024考研调剂须知

----------------------------------------------------------------------------------------------------- 考研复试科研背景提升班 教你快速深入了解掌握考研复试面试中的常见问题以及注意事项&#xff0c;系统的教你如何在短期内快速提升自己的专业知识水平和编程以及英语…

Python+Django+Html网页版人脸识别考勤打卡系统

程序示例精选 PythonDjangoHtml人脸识别考勤打卡系统 如需安装运行环境或远程调试&#xff0c;见文章底部个人QQ名片&#xff0c;由专业技术人员远程协助&#xff01; 前言 这篇博客针对《PythonDjangoHtml网页版人脸识别考勤打卡系统》编写代码&#xff0c;代码整洁&#xf…

单链表总结提升

这篇博客讲解数据结构中的单链表&#xff0c;包括单链表的基础知识和我对链表实现的总结理解&#xff0c;希望可以帮助到正在学习的小伙伴&#xff0c;也希望得到小伙伴们的关注和支持哦~ 目录 1.单链表的概念 1.2顺序表和链表的对比 顺序表&#xff1a; 链表&#xff1a;…

Sketch3D:用于草图到3D生成的样式一致性指南

Sketch3D: Style-Consistent Guidance for Sketch-to-3D Generation Sketch3D&#xff1a;用于草图到3D生成的样式一致性指南 Wangguandong Zheng 重试 错误原因 Southeast UniversityChina 重试 错误原因 wgdzhengseu.edu.cnHaifeng Xia 重试 错误原因 Southeast Universit…

C语言读取 .ico 文件并显示数据

原来是想做光标编辑器&#xff0c;自己把绘图板的内容导出为光标格式 鼠标指针文件格式解析——Windows&#xff08;一&#xff09; (qq.com) 代码来源自 Icons | Microsoft Learn 鄙人又补充些变量可以运行微软的代码 简单代码如下 #include <stdio.h> #include &l…

软考高级架构师:数据库模式概念和例题

一、AI 讲解 数据库模式分为三个层次&#xff1a;外模式、概念模式和内模式。这三个层次分别对应不同的抽象级别&#xff0c;帮助数据库管理员和用户以不同的视角理解数据库结构。 外模式&#xff08;用户级&#xff09;&#xff1a;是数据库用户的视图。每个用户可以通过外模…

最新Android Studio导入aar包的方法

以前的方式&#xff0c;目前看网上也大多数都是这种方式&#xff0c;导致我本地加的时候一直有问题 但是这样都无法sync以及编译通过&#xff0c;因为方式已经变了 1&#xff1a;将aar文件复制到MyApplication\app\libs下 2&#xff1a;在MyApplication\app\build.gradle下添加…

LeetCode-Java:6.Z字形变换

文章目录 题目解① 找规律 题目 将一个给定字符串 s 根据给定的行数 numRows &#xff0c;以从上往下、从左到右进行 Z 字形排列。 比如输入字符串为 "PAYPALISHIRING" 行数为 3 时&#xff0c;排列如下&#xff1a; P A H N A P L S I I G Y I R之后&a…