LeetCode 热题 100 | 二叉树(二)
目录
1 543. 二叉树的直径
2 102. 二叉树的层序遍历
3 108. 将有序数组转换为二叉搜索树
菜鸟做题,语言是 C++
1 543. 二叉树的直径
这道题和 124. 二叉树中的最大路径和 太像了
题眼:二叉树的 直径 是指树中任意两个节点之间 最长路径的长度 。
简而言之,就是找出一条路径,且这条路径上的节点最多。
解题思路:
- 从下往上遍历二叉树
- 当前子树中的最长路径 = 1 + 左子树中的最长路径 + 右子树中的最长路径
- 向父节点自荐当前子树中的最长路径 = 1 + max(左子树中的最长路径,右子树中的最长路径)
为什么必须从 “左子树中的最长路径” 和 “右子树中的最长路径” 中选一个?不能都要吗?当然不行。我们要的是一条笔直的路径,如果左右子树都带上,那不就分叉了吗。
思路说明图:

对于绿色节点,在它作为根节点的子树中,最长路径 = 1 + 左子树中的最长路径 + 右子树中的最长路径;绿色节点(左子节点)向蓝色节点(父节点)自荐,自荐的最长路径 = 1 + max(左子树中的最长路径,右子树中的最长路径)。对于蓝色节点,在它作为根节点的子树中,最长路径 = 1 + 左子树中的最长路径 + 右子树中的最长路径。以此类推。
class Solution {
public:int ans = 1;int helper(TreeNode * root) {if (!root) return 0;int ltree = helper(root->left);int rtree = helper(root->right);ans = max(ans, 1 + ltree + rtree);return 1 + max(ltree, rtree);}int diameterOfBinaryTree(TreeNode* root) {helper(root);return ans - 1;}
};
说明:我们算的其实是最多节点数,而路径长度是边的条数,因此需要减一:
return ans - 1;
2 102. 二叉树的层序遍历
是循环,不是递归
层序遍历:逐层地,从左到右访问所有节点。

解题思路:
- 出队:从左到右遍历当前层中的每个节点
- 入队:将每个节点的左右子节点存入队列中
- 出队:从左到右遍历左右子节点,即下一层中的每个节点
具体代码:
① 循环条件:当队列中还有节点没有被遍历时,即队列长度不为 0 时。
while (q.size()) {}
② 遍历某一层中的所有节点:
int currentLevelSize = q.size();
for (int i = 0; i < currentLevelSize; ++i) {TreeNode * node = q.front();q.pop();// ...
}
此时队列的大小等于当前层中的节点个数。
③ 存入每个节点的左右子节点,即下一层中的所有节点。
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
只有节点不为空时才需要被访问。
class Solution {
public:vector<vector<int>> levelOrder(TreeNode* root) {if (!root) return {};vector<vector<int>> ans;queue<TreeNode *> q;q.push(root);while (q.size()) {int currentLevelSize = q.size();ans.push_back(vector<int> ());for (int i = 0; i < currentLevelSize; ++i) {TreeNode * node = q.front();q.pop();ans.back().push_back(node->val);if (node->left) q.push(node->left);if (node->right) q.push(node->right);}}return ans;}
};
3 108. 将有序数组转换为二叉搜索树
与对 105. 从前序与中序遍历序列构造二叉树 的理解有一点点像
可以理解成:将有序数组视为中序遍历的结果,并将其还原回二叉树。
中序遍历的结果数组的特点:(左子树,根节点,右子树)
题眼:高度平衡二叉树 是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。因此,我们每次都取数组区间的中间值为根节点,代码如下:
int mid = (left + right) / 2;
完整代码:
class Solution {
public:TreeNode* helper(vector<int>& nums, int left, int right) {if (left > right) return nullptr;int mid = (left + right) / 2;TreeNode* root = new TreeNode(nums[mid]);root->left = helper(nums, left, mid - 1);root->right = helper(nums, mid + 1, right);return root;}TreeNode* sortedArrayToBST(vector<int>& nums) {return helper(nums, 0, nums.size() - 1);}
};
相关文章:
LeetCode 热题 100 | 二叉树(二)
目录 1 543. 二叉树的直径 2 102. 二叉树的层序遍历 3 108. 将有序数组转换为二叉搜索树 菜鸟做题,语言是 C 1 543. 二叉树的直径 这道题和 124. 二叉树中的最大路径和 太像了 题眼:二叉树的 直径 是指树中任意两个节点之间 最长路径的长度 。…...
mini-spring|定义标记类型Aware接口,实现感知容器对象
**前言:**如果我们想获得 Spring 框架提供的 BeanFactory、ApplicationContext、BeanClassLoader等这些能力做一些扩展框架的使用时该怎么操作呢。所以我们本章节希望在 Spring 框架中提供一种能感知容器操作的接口,如果谁实现了这样的一个接口ÿ…...
83. 删除排序链表中的重复元素
给定一个已排序的链表的头 head , 删除所有重复的元素,使每个元素只出现一次 。返回 已排序的链表 。 输入:head = [1,1,2] 输出:[1,2] 输入:head = [1,1,2,3,3] 输出:[1,2,3] 提示: 链表中节点数目在范围 [0, 300] 内-100 <= Node.val <= 100题目数据保证链表已…...
贪心算法
贪心算法 例题1、股票买卖题目信息思路题解 2、货仓选址题目信息思路题解 3、糖果传递题目信息思路题解 4、雷达设备题目信息思路题解 例题 1、股票买卖 题目信息 思路 相邻两天,后>前,则交易一次 题解 #include <bits/stdc.h> #define en…...
MySQL基本知识
目录 一,MySQL的元数据库 1.1.什么是元数据库 1.2.有哪些元数据库 1.3.切换数据库 二,账户管理 2.1.设置权限 2.2.授权用户 2.3.查看权限 2.4.撤销权限 三,MySQL引擎 3.1什么是数据库引擎 3.2.查看数据引擎 3.3.MyISAM引擎 3.4…...
Vue3 (unplugin-auto-import自动导入的使用)
安装 参考链接 npm i -D unplugin-auto-importvite.config.ts里面配置 import AutoImport from unplugin-auto-import/viteAutoImport({imports:[ vue,vue-router]})重新运行项目会生成一个auto-imports.d.ts的文件 /* eslint-disable */ /* prettier-ignore */ // ts-nochec…...
【漏洞复现】大华智慧园区综合管理平台信息泄露漏洞
Nx01 产品简介 大华智慧园区综合管理平台是一款综合管理平台,具备园区运营、资源调配和智能服务等功能。该平台旨在协助优化园区资源分配,满足多元化的管理需求,同时通过提供智能服务,增强使用体验。 Nx02 漏洞描述 大华智慧园区…...
JavaScript的书写方式
JavaScript的书写方式 目前较为流行的是第二种和第三种,第一种很少见。在第二种和第三种推荐使用第三种,因为在日常开发/工作中,第三种是最为常见的 1.行内式 把JS代码嵌入到html元素内部 示例代码 运行效果 由于JS中字符串常量可以使用单引…...
第二十篇-推荐-纯CPU(E5-2680)推理-llama.cpp-qwen1_5-72b-chat-q4_k_m.gguf
环境 系统:CentOS-7 CPU: Intel Xeon CPU E5-2680 v4 2.40GHz 14C28T 内存: 48G DDR3 依赖安装 make --version GNU Make 4.3gcc --version gcc (GCC) 11.2.1 20220127 (Red Hat 11.2.1-9)g --version g (GCC) 11.2.1 20220127 (Red Hat …...
CSS常见选择器
CSS常见选择器 在Web开发中,层叠样式表(CSS)是用于描述HTML或XML(包括SVG和XHTML等其他XML语言)文档的样式的语言。CSS描述了文档的表现形式,包括布局、颜色和字体等。在CSS中,选择器是一种模式…...
[LWC] Components Communication
目录 Overview Summary Sample Code 1. Parent -> Child - Public Setter / Property / Function a. Public Property b. Public getters and setters c. Public Methods 2. Child -> Parent - Custom Event 3. Unrelated Components - LMS (Lightning Message…...
Unity中URP实现水体(水下的扭曲)
文章目录 前言一、使用一张法线纹理,作为水下扭曲的纹理1、在属性面板定义一个纹理,用于传入法线贴图2、在Pass中,定义对应的纹理和采样器3、在常量缓冲区,申明修改 Tilling 和 Offset 的ST4、在顶点着色器,计算得到 应…...
anaconda指定目录创建环境无效/环境无法创建到指定位置
已经设置目录到D盘 创建环境时还是分配到C盘 可能是指定位置没有开启读写权限,如我在这里安装到了anaconda文件夹,则打开该文件夹的属性->安全->编辑 allusers下的权限全都打勾...
《Docker极简教程》--Docker在生产环境的应用--Docker在生产环境的部署
一、准备工作 1.1 硬件和基础设施要求 硬件和基础设施要求是在部署 Docker 到生产环境之前需要认真考虑和准备的重要方面,以下是一般性的要求: 服务器硬件: CPU:建议使用多核处理器,以支持同时运行多个容器。内存&a…...
算法D31 | 贪心算法1 | 455.分发饼干 376. 摆动序列 53. 最大子序和
贪心算法其实就是没有什么规律可言,所以大家了解贪心算法 就了解它没有规律的本质就够了。 不用花心思去研究其规律, 没有思路就立刻看题解。 基本贪心的题目 有两个极端,要不就是特简单,要不就是死活想不出来。 学完贪心之后再…...
在IDEA中创建vue hello-world项目
工作中最近在接触vue前端项目,记录一下从0搭建一个vue hello world项目的步骤 1、本地电脑安装配置node、npm D:\Project\vue\hello-world>node -v v14.21.3 D:\Project\vue\hello-world>npm -v 6.14.18 D:\Project\vue\hello-world> 2、设置npm国内淘…...
如何获取pnpm存储目录
现在你可以做 得到:\path\to.pnpm-store\v3 pnpm store path注:从v7.0.0开始,pnpm 存储位于不同的文件夹中。它将位于$XDG_DATA_HOMELinux Linux : ~/.local/share/pnpm/store (default) Windows : C:\Users\YOUR_NAME\AppData\Local\pn…...
QT两个类之间使用信号槽
在做一些东西的时候,习惯性的引入头文件并且调用,因此出现了很多bug,qt的信号槽机制便可以有效的避免一些问题。 A类 #ifndef A_H #define A_H#include <QObject> #include <QDebug> class A : public QObject {Q_OBJECT public:explicit A…...
【Ubuntu】使用WSL安装Ubuntu
WSL 适用于 Linux 的 Windows 子系统 (WSL) 是 Windows 的一项功能,可用于在 Windows 计算机上运行 Linux 环境,而无需单独的虚拟机或双引导。 WSL 旨在为希望同时使用 Windows 和 Linux 的开发人员提供无缝高效的体验。安装 Linux 发行版时,…...
【Node.js】自动生成 API 文档
目录 1、直接使用swagger-ui-express 2、配合swagger-jsdoc 如何在Node.js项目中使用 Swagger 来自动生成 API接口文档,使用生成方式有很多种。本文基于swagger-jsdocswagger-ui-express快速实现 1、直接使用swagger-ui-express // 方便来浏览和测试api npm i sw…...
Linux应用开发之网络套接字编程(实例篇)
服务端与客户端单连接 服务端代码 #include <sys/socket.h> #include <sys/types.h> #include <netinet/in.h> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <arpa/inet.h> #include <pthread.h> …...
跨链模式:多链互操作架构与性能扩展方案
跨链模式:多链互操作架构与性能扩展方案 ——构建下一代区块链互联网的技术基石 一、跨链架构的核心范式演进 1. 分层协议栈:模块化解耦设计 现代跨链系统采用分层协议栈实现灵活扩展(H2Cross架构): 适配层…...
MODBUS TCP转CANopen 技术赋能高效协同作业
在现代工业自动化领域,MODBUS TCP和CANopen两种通讯协议因其稳定性和高效性被广泛应用于各种设备和系统中。而随着科技的不断进步,这两种通讯协议也正在被逐步融合,形成了一种新型的通讯方式——开疆智能MODBUS TCP转CANopen网关KJ-TCPC-CANP…...
【2025年】解决Burpsuite抓不到https包的问题
环境:windows11 burpsuite:2025.5 在抓取https网站时,burpsuite抓取不到https数据包,只显示: 解决该问题只需如下三个步骤: 1、浏览器中访问 http://burp 2、下载 CA certificate 证书 3、在设置--隐私与安全--…...
GC1808高性能24位立体声音频ADC芯片解析
1. 芯片概述 GC1808是一款24位立体声音频模数转换器(ADC),支持8kHz~96kHz采样率,集成Δ-Σ调制器、数字抗混叠滤波器和高通滤波器,适用于高保真音频采集场景。 2. 核心特性 高精度:24位分辨率,…...
HashMap中的put方法执行流程(流程图)
1 put操作整体流程 HashMap 的 put 操作是其最核心的功能之一。在 JDK 1.8 及以后版本中,其主要逻辑封装在 putVal 这个内部方法中。整个过程大致如下: 初始判断与哈希计算: 首先,putVal 方法会检查当前的 table(也就…...
嵌入式学习笔记DAY33(网络编程——TCP)
一、网络架构 C/S (client/server 客户端/服务器):由客户端和服务器端两个部分组成。客户端通常是用户使用的应用程序,负责提供用户界面和交互逻辑 ,接收用户输入,向服务器发送请求,并展示服务…...
【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 日志分析…...
华为OD最新机试真题-数组组成的最小数字-OD统一考试(B卷)
题目描述 给定一个整型数组,请从该数组中选择3个元素 组成最小数字并输出 (如果数组长度小于3,则选择数组中所有元素来组成最小数字)。 输入描述 行用半角逗号分割的字符串记录的整型数组,0<数组长度<= 100,0<整数的取值范围<= 10000。 输出描述 由3个元素组成…...
Windows电脑能装鸿蒙吗_Windows电脑体验鸿蒙电脑操作系统教程
鸿蒙电脑版操作系统来了,很多小伙伴想体验鸿蒙电脑版操作系统,可惜,鸿蒙系统并不支持你正在使用的传统的电脑来安装。不过可以通过可以使用华为官方提供的虚拟机,来体验大家心心念念的鸿蒙系统啦!注意:虚拟…...
