【LeetCode热题100】--543.二叉树的直径

543.二叉树的直径

给你一棵二叉树的根节点,返回该树的 直径

二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root

两节点之间路径的 长度 由它们之间边数表示。

image-20231003083307846

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

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

image-20231003083334098

如图我们可以知道路径 [9, 4, 2, 5, 7, 8] 可以被看作以 2 为起点,从其左儿子向下遍历的路径 [2, 4, 9] 和从其右儿子向下遍历的路径 [2, 5, 7, 8] 拼接得到。

假设我们知道对于该节点的左儿子向下遍历经过最多的节点数 L (即以左儿子为根的子树的深度) 和其右儿子向下遍历经过最多的节点数 R(即以右儿子为根的子树的深度),那么以该节点为起点的路径经过节点数的最大值即为 L+R+1

记节点node为起点的路径经过节点数的最大值为 d n o d e d_{node} dnode,那么二叉树的直径就是所有 d n o d e d_{node} dnode的最大值减一

最后的算法流程为:定义一个递归函数 d e p t h ( n o d e ) depth(node) depth(node),计算 d n o d e d_{node} dnode,函数返回该节点为根的子树的深度,先递归调用左儿子和右儿子求得它们为根的子树的深度L和R,则该节点为根的子树的深度即为 m a x ( L , R ) + 1 max(L,R)+1 max(L,R)+1,该节点的 d n o d e d_{node} dnode值为L+R+1

递归搜索每个节点并设一个全局变量ans记录 d n o d e d_{node} dnode的最大值,最后返回ans-1即为树的直径

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
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/147057.html

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

相关文章

2024免费的硬盘数据恢复软件有哪些?

在当今信息化的社会,数据成为了人们日常工作和生活的重要组成部分。不幸的是,数据丢失的问题也越来越普遍。硬盘数据恢复软件因此而产生,为那些不幸丢失数据的人们提供了救赎。在本文中,我们将介绍十大硬盘数据恢复软件。 一、Rec…

matplotlib从起点出发(9)_Tutorial_9_cycler

0 需求 绘图时有时需要指定几种颜色,或者线型,我们统称为样式,让绘制出的内容在这些样式中循环配置。这时就需要使用到本文所提到的技巧,即cycler. 1 进入教程 本文是自定义属性循环(cycler)设置的演示,用于控制多线…

格点数据可视化(美国站点的日降雨数据)

获取美国站点的日降雨量的格点数据,并且可视化 导入模块 from datetime import datetime, timedelta from urllib.request import urlopenimport cartopy.crs as ccrs import cartopy.feature as cfeature import matplotlib.colors as mcolors import matplotli…

【面试总结大纲】

面试 springSpring AOP的具体实现核心概念分别指的是什么?基于注解的切面实现主要包括以下几个步骤:两个切面,它们之间的顺序是怎么控制的 springmvc的工作流程设计模式原则Spring 框架中用到了哪些设计模式? spring Spring AOP的具体实现 …

Nginx之Openresty基本使用解读

目录 Openresty基本介绍 Openresty源码编译安装 Openresty基本使用 测试lua脚本 外部分文件导入 关闭缓存,开启热部署 用lua代码获取系统变量 Openresty基本介绍 OpenResty是一个基于 Nginx 与 Lua 的高性能 Web 平台,其内部集成了大量精良的 Lua…

【MySQL教程】| (1-1) 2023MySQL-8.1.0 安装教程

文章目录 一、安装包下载二、安装配置1、解压安装包2、编写MySQL配置文件3、初始化MySQL数据库3、安装mysql服务并启动4、MySQL服务5、连接MySQL6、修改密码 三、配置环境变量四、防止mysql自启动拖慢开机时间 近日有粉丝问到mysql在win11的安装中遇到一些问题,应粉…

[MAUI程序设计] 用Handler实现自定义跨平台控件

今天来谈一谈MAUI跨平台技术的核心概念——跨平台控件。 无论是MAUI,Xamarin.Forms还是其它的跨平台技术,他们是多个不同平台功能的抽象层,利用通用的方法实现所谓“一次开发,处处运行”。 跨平台框架需要考虑通用方法在各平台的兼容,但由于各原生平台(官方将原生称为本…

RTP/RTCP 协议讲解

文章目录 前言一、RTP 协议1、RTP 协议概述2、RTP 工作机制3、RTP 协议的报文结构4、wireshark 抓取 RTP 报文 二、RTCP 协议1、RTCP 协议概述2、RTCP 工作机制3、RTCP 数据报4、wireshark 抓取 RTCP 报文 三、RTSP 和 RTP 的关系四、易混淆概念1、RTP over UDP 和 RTP over RT…

K8s架构简述

以部署一个nginx服务说明kubernetes系统各个组件调用关系: 一旦kubernetes环境启动之后,master和node都会将自身的信息存储到etcd数据库中 一个nginx服务的安装请求会首先被发送到master节点的apiServer组件 apiServer组件会调用scheduler组件来决定到底…

Linux系统编程系列之线程

一、什么是线程 线程(Thread)是计算机中的基本执行单元,是操作系统调度的最小单位。线程是进程内的一个独立执行流程,一个进程可以包含多个线程,这些线程共享进程的资源,但每个线程都有自己的独立栈空间以及…

【day11.02】网络编程脑图

大小端存储: ip地址划分:

【小沐学前端】从零开始搭建一个Vue项目

文章目录 1、简介1.1 Vue 核心功能1.2 Vue API风格1.3 node环境 2、构建项目2.1 vue create2.2 vue ui2.3 vue init2.4 vite 结语 1、简介 Vue (发音为 /vjuː/,类似 view) 是一款用于构建用户界面的 JavaScript 框架。它基于标准 HTML、CSS 和 JavaScript 构建&am…

华为云云耀云服务器L实例评测|部署在线轻量级备忘录 memos

华为云云耀云服务器L实例评测|部署在线轻量级备忘录 memos 一、云耀云服务器L实例介绍1.1 云服务器介绍1.2 产品优势1.3 应用场景1.4 支持镜像 二、云耀云服务器L实例配置2.1 重置密码2.2 服务器连接2.3 安全组配置 三、部署 memos3.1 memos介绍3.2 Docker 环境搭建…

OSI体系结构和TCP/IP体系结构

在第一章( 计网第一章 )的时候,曾经提到过OSI体系结构和TCP/IP体系结构,并对它们进行了简单的对比。这篇博客在其基础上进行更深层次的理解。 一.OSI体系结构: 通信子网: 计算机网络在逻辑功能上可以分为…

Redis主从复制、哨兵模式、群集部署

目录 一、Redis高可用 二、Redis主从复制 主从复制的作用 主从复制的流程 实例 三、Redis哨兵模式 哨兵的核心功能 哨兵模式的作用 哨兵结构的组成 故障转移机制 实例 四、Redis群集 集群的作用,可以归纳为两点: Redis集群的数据分片&#…

wireshark of tshark tools v3.4.0版本 支持json

tshark(1) Install tshark (Wireshark) Ver.3.4.0 on CentOS7 --It must be "ps", "text", "pdml", "psml" or "fields". TCP 协议中的三次握手和四次挥手是 TCP 连接建立和关闭的过程。 三次握手 客户端向服务器发送 SYN…

Python绘图系统25:新增8种绘图函数

文章目录 常用绘图函数单选框的更改逻辑源代码 Python绘图系统: 前置源码: Python打造动态绘图系统📈一 三维绘图系统 📈二 多图绘制系统📈三 坐 标 轴 定 制📈四 定制绘图风格 📈五 数据生成导…

自动混剪多段视频、合并音频、添加文案的技巧分享

在如今的社交媒体时代,视频的重要性越来越被人们所重视。许多人喜欢记录生活中的美好瞬间,并将其制作成视频分享给朋友和家人。然而,对于那些拍摄了大量视频的人来说,一个一个地进行剪辑和合并可能是一项令人头痛的任务。但是&…

GraphQL全面深度讲解

目录 一、GraphQL 是什么 二、GraphQL 规范 数据模型 字段 参数 三、运行示例 四、优势和劣势 优势 劣势 一、GraphQL 是什么 GraphQL 是一种用于 API 的查询语言,也是一个基于服务端的运行引擎。 GraphQL 提供了一套完整的规范和描述用于查询 API&#xf…

一种基于体素的射线检测

效果 基于体素的射线检测 一个漏检的射线检测 从起点一直递增指定步长即可得到一个稀疏的检测 bool Raycast(Vector3 from, Vector3 forword, float maxDistance){int loop 6666;Vector3 pos from;Debug.DrawLine(from, from forword * maxDistance, Color.red);while (loo…