LeetCodehot100 力扣热题100 二叉树展开为链表
代码思路
目标：
将二叉树展平（flatten）为一个单链表。展平后的链表应该按照前序遍历的顺序排列节点，即：
• 节点的左子树指针设置为 nullptr。
• 节点的右子树指针指向下一个节点。
代码注释及思路
class Solution {public:// flatten函数：将二叉树转化为链表void flatten(TreeNode* root) {vector<TreeNode*> l; // 用来存储前序遍历的节点preorderTraversal(root, l); // 先进行前序遍历并将节点加入到l中int n = l.size(); // 记录前序遍历中节点的个数// 连接所有节点，使其形成链表for (int i = 1; i < n; i++) {TreeNode *prev = l.at(i - 1), *curr = l.at(i);prev->left = nullptr; // 将前一个节点的左指针置为NULLprev->right = curr; // 将前一个节点的右指针指向当前节点}}// preorderTraversal函数：前序遍历二叉树，并将每个节点加入到vector l中void preorderTraversal(TreeNode* root, vector<TreeNode*> &l) {if (root != NULL) { // 如果当前节点不为空l.push_back(root); // 将当前节点加入到vector lpreorderTraversal(root->left, l); // 递归遍历左子树preorderTraversal(root->right, l); // 递归遍历右子树}}};l.at(i - 1) 和 l[i - 1] 在大多数情况下会表现得很相似，但它们有一些关键的区别，主要体现在安全性和异常处理上。
1. l.at(i - 1)
• 安全性：at() 是 std::vector 的一个成员函数，它会检查你传入的索引是否越界。如果索引超出了有效范围，它会抛出一个 std::out_of_range 异常。
• 行为：如果你访问了一个无效索引（比如负数或者超出了 vector 的大小），at() 会立即抛出异常，从而帮助你捕捉潜在的错误。
std::vector<int> v = {10, 20, 30, 40};
try {
std::cout << v.at(5) << std::endl; // 抛出 std::out_of_range 异常
} catch (const std::out_of_range& e) {
std::cout << "Out of range: " << e.what() << std::endl; // 会打印异常信息
}
2. l[i - 1]
• 安全性：operator[] 是 std::vector 的索引访问方式，它不会做越界检查。如果你使用一个无效的索引，它不会抛出异常，而是会产生未定义行为，可能导致程序崩溃、访问到非法内存等问题。
• 行为：即使访问了一个超出范围的索引，它也不会报错，而是直接返回一个非法的内存位置。
std::vector<int> v = {10, 20, 30, 40};
std::cout << v[5] << std::endl; // 未定义行为，可能导致程序崩溃或异常
• at(i)：比 operator[] 更安全，因为它会进行边界检查并抛出异常。
• operator[]：更加高效，因为没有进行边界检查，但使用不当会导致程序崩溃或产生不可预料的行为。
哪个更好？
• 如果你确定索引是有效的，或者你对代码的安全性非常关注，使用 operator[] 会更高效。
• 如果你更关心代码的安全性，尤其是在你不确定索引是否有效的情况下，使用 at() 更加可靠。
详细思路
1. 前序遍历：
• 在 flatten 函数中，首先调用 preorderTraversal 对二叉树进行前序遍历。前序遍历的顺序是：根节点 → 左子树 → 右子树。
• 在 preorderTraversal 函数中，当访问一个节点时，将它加入到一个 vector<TreeNode*>（即 l）中。
• 递归进行左子树和右子树的遍历。
2. 重建链表：
• 在完成前序遍历后，l 中存储了按前序遍历顺序排列的所有节点。
• 接下来，遍历这个 l，并对每一对相邻节点（prev 和 curr）做以下操作：
• 将 prev 节点的左指针置为 nullptr。
• 将 prev 节点的右指针指向 curr 节点。
• 这样，我们将树的结构变为链表，且节点按照前序遍历顺序排列。
运行步骤
假设输入的二叉树如下：
1
/ \
2 5
/ \ \
3 4 6
1. 调用 flatten(root)，传入根节点 1。
2. 调用 preorderTraversal(root, l)，此时开始前序遍历：
• l = [1]（根节点 1）
• 遍历左子树，l = [1, 2]
• 遍历 2 的左子树，l = [1, 2, 3]
• 遍历 2 的右子树，l = [1, 2, 3, 4]
• 遍历右子树，l = [1, 2, 3, 4, 5]
• 遍历 5 的右子树，l = [1, 2, 3, 4, 5, 6]
3. 现在，l = [1, 2, 3, 4, 5, 6]，即按前序遍历顺序排列的节点。
4. 接着，连接这些节点：
• prev = 1, curr = 2 → 1->left = nullptr, 1->right = 2
• prev = 2, curr = 3 → 2->left = nullptr, 2->right = 3
• prev = 3, curr = 4 → 3->left = nullptr, 3->right = 4
• prev = 4, curr = 5 → 4->left = nullptr, 4->right = 5
• prev = 5, curr = 6 → 5->left = nullptr, 5->right = 6
最终的链表结构如下：
1 -> 2 -> 3 -> 4 -> 5 -> 6
复杂度分析
• 时间复杂度：O(n)，其中 n 是树中节点的数量。我们对树进行了一次前序遍历，遍历过程的时间复杂度是 O(n)。在重新连接节点时，也只需要遍历一次 l。
• 空间复杂度：O(n)，主要是用于存储前序遍历结果的 vector l，其大小为 n。递归栈的深度是树的高度，最坏情况下是 O(n)，最好的情况下是 O(log n)（如果树是平衡的）。
相关文章：
LeetCodehot100 力扣热题100 二叉树展开为链表
代码思路 目标： 将二叉树展平（flatten）为一个单链表。展平后的链表应该按照前序遍历的顺序排列节点，即： • 节点的左子树指针设置为 nullptr。 • 节点的右子树指针指向下一个节点。 代码注释及思路 class Solution…...
备战蓝桥杯 Day1 回顾语言基础
开启蓝桥杯刷题之路 Day1 回顾语言基础 1.配置dev 工具->编译选项->勾选编译时加入以下命令->设定编译器配置(release和debug)都要-> -stdc11 ->代码生成/优化->代码生成/优化->语言标准(-std)->ISO C11 ->代码警告->显示最多警告信息(-Wall)…...
基于Ceedling的嵌入式软件单元测试
Ceedling 如果你使用 Ceedling（一个针对 C 代码单元测试的构建管理器），可以更方便地管理测试。Ceedling 会自动处理 Unity 和 CMock 的集成，无需手动编写 Makefile。 1.环境搭建 1.1 Ruby环境 sudo apt-get install ruby1.2 安…...
聊一聊FutureTask源码中体现的“自旋锁”思想
前言 这篇文章记录了笔者自己对FutureTask的部分源码设计的思考与心得，属于笔者自己的观点，若有哪位热爱源码研究的同仁觉得我说的不对，欢迎批评指正。 提示：在阅读之前必须对FutureTask的源码和实现原理有一定的了解。本文要聊…...
自有证书的rancher集群使用rke部署k8s集群异常
rancher使用自签域名，或者商业证书容易踩到的坑。 最开始的报错： docker logs kubelet‘s id E0214 13:04:14.590268 9614 pod_workers.go:1300] "Error syncing pod, skipping" err"failed to \"StartContainer\" for …...
LabVIEW外腔二极管激光器稳频实验
本项目利用LabVIEW软件开发了一个用于外腔二极管激光器稳频实验的系统。系统能够实现激光器频率的稳定控制和实时监测，为激光实验提供了重要支持。 项目背景： 系统解决了外腔二极管激光器频率不稳定的问题，以满足对激光器频率稳定性要求较高…...
使用docker compose启动postgres并设置时区
设置PostGres时区 方法 1: 使用 POSTGRES_INITDB_ARGS 设置时区方法 2: 使用初始化脚本设置时区创建 init-user-db.sql更新 docker-compose.yml 启动服务 要在启动 PostgreSQL 数据库时设置时区，可以通过在 docker-compose.yml 文件中添加环境变量或通过配置文件来实…...
杜绝遛狗不牵绳，AI技术助力智慧城市宠物管理
在我们的生活中，宠物扮演着越来越重要的角色。然而，随着养宠人数的增加，一系列问题也随之而来，如烈性犬伤人、遛狗不牵绳、流浪犬泛滥等。这些问题不仅影响了社会秩序，也给宠物本身带来了安全隐患。幸运的是࿰…...
【ISO 14229-1:2023 UDS诊断全量测试用例清单系列：第二十节】
ISO 14229-1:2023 UDS诊断服务测试用例全解析（WriteMemoryByAddress_0x3D服务） 作者：车端域控测试工程师 更新日期：2025年02月14日 关键词：UDS协议、0x3D服务、内存写入、ISO 14229-1:2023、ECU测试 一、服务功能概述…...
[npm install 报错] Verion 9 of Highlight.js has reached EOL
1、在项目中执行npm install 报错 Verion 9 of Highlight.js has reached EOL,如下图: 2、报错原因 Highlight.js 不再支持10以前的版本，需下载10及之后的版本 3、解决办法 打开项目中的package.json文件，将highlight.js的版本修改为:10.7.2,删除node…...
Flutter Gradle 命令式插件正式移除，你迁移旧版 Gradle 配置了吗？
在 Flutter 3.29 版本里官方正式移除了 Flutter Gradle Apply 插件，其实该插件自 3.19 起已被弃用，同时 Flutter 团队后续也打算把 Flutter Gradle 从 Groovy 转换为 Kotlin，并将其迁移到使用 AGP（Android Gradle Pluginÿ…...
CCF-GESP 等级考试 2024年9月认证C++二级真题解析
2024年9月真题 一、单选题（每题2分，共30分） 正确答案：A 考察知识点：计算机存储 解析：磁心存储元件是早期计算机中用于存储数据的部件，它和现代计算机中的内存功能类似，都是用于临时…...
CubeMX配置STM32L071KZT6
明确需要配置的项 下面是工作中遇到某个项目提炼出来的的功能需求。其中MCU选用STM32L071KZT6。 名称 标识 IO功能 对应引脚 备注 蜂鸣器 BUZZER 开关量输出 PA2 指示灯 LED-R PA15 LED-G PA12 LED-Y PA11 按键 KEY-1 开关量输入 PB5 外…...
RadASM环境，win32汇编入门教程之二
;win32汇编环境，RadAsm入门教程之二 ;前面我们已经学了教程一，生成了第一个软件。那么让我们继续我们的学习旅程。本教程讲解一下基本窗口模版的原理。让我们打开RadASM后，双击右侧的ABC.Asm文件，一点点研究。 ;首先，我…...
mysql开启gtid并配置主从
默认主从都开启了bin log. 1.主从都在/etc/my.cnf中加入并重启服务 gtid_mode ON enforce_gtid_consistency ON 2.在主库创建用户并授权 create user slave identified with mysql_native_password by 123456 mysql>GRANT REPLICATION SLAVE ON *.* to slave% identified…...
RAG科普文！检索增强生成的技术全景解析
RAG 相关技术的八个主题：https://pub.towardsai.net/a-taxonomy-of-retrieval-augmented-generation-a39eb2c4e2ab 增强生成 (RAG) 是塑造应用生成式 AI 格局的关键技术。Lewis 等人在其开创性论文中提出了一个新概念面向知识密集型 NLP 任务的检索增强生成之后&…...
【Sceneform-EQR】实现3D场景背景颜色的定制化（背景融合的方式、Filament材质定制）
写在前面的话 Sceneform-EQR是基于（filament）扩展的一个用于安卓端的渲染引擎。故本文内容对Sceneform-EQR与Filament都适用。 需求场景 在使用Filament加载三维场景的过程中，一个3D场景对应加载一个背景纹理。而这样的话，即便…...
python自动化测试之统一请求封装及通过文件实现接口关联
一、接口文档怎么看？ http://www.aaa.com/api.php?sindex/index&applicationapp&application_client_typeweixi n&tokentokenvalue&ajaxajax 参数解释： http 协议 www.aaa.com IP和端口 api.php 接口的地址 sindex/index 接口名称以 …...
Redis笔记
文章目录 Redis笔记通用命令get和setkeysexistsdelexpirettlRedis的key过期策略定时器的实现原理type 持久化RDB(Redis DataBase)---定期备份bgsave AOF(Append Only File)---实时备份 Redis笔记 Redis是一个“客户端-服务器”结构的程序，客户端和服务器之间通过网…...
repo学习使用
Repo 是以 Git 为基础构建的代码库管理工具。Repo 可以在必要时整合多个 Git 代码库，将相关内容上传到版本控制系统。借助单个 Repo 命令，可以将文件从多个代码库下载到本地工作目录。 Repo 命令是一段可执行的 Python 脚本，你可以将其放在路…...
windows 通过docker 安装mysql
参考：Docker安装并使用Mysql（可用详细）_docker 安装mysql-CSDN博客 1. 拉取镜像：docker pull mysql:5.7 2. 查看镜像：docker image 3. 创建mysql 容器实例，并将data 目录挂载到本地d盘上 docker run --n…...
高效利用Python爬虫开发批量获取商品信息
在当今电商行业竞争激烈的环境下，精准且高效地获取商品信息对于商家和数据分析师来说至关重要。无论是进行市场调研、优化商品布局，还是制定竞争策略，商品信息的全面掌握都是关键。Python爬虫技术以其强大的功能和灵活性，成为批量…...
【C语言】左旋字符串（三种实现方式）
题目： 实现一个函数，可以左旋字符串中的k个字符。 例如： ABCD左旋一个字符得到BCDA ABCD左旋两个字符得到CDAB 方法一： 我们画个图分析一下： 基本逻辑： 就是我们每一次旋转之前，我们就取出…...
Spring Security，servlet filter，和白名单之间的关系
首先，Servlet Filter是Java Web应用中的基础组件，用于拦截请求和响应，进行预处理和后处理。它们在处理HTTP请求时处于最外层，可以执行日志记录、身份验证、授权等操作。白名单机制通常指允许特定IP、用户或请求通过的安全策略&…...
Python 调用 Azure OpenAI API
在人工智能和机器学习快速发展的今天，Azure OpenAI 服务为开发者提供了强大的工具来集成先进的 AI 能力到他们的应用中。本文将指导您如何使用 Python 调用 Azure OpenAI API，特别是使用 GPT-4 模型进行对话生成。 准备工作 在开始之前，请确保您已经： 拥有一个 Azure 账户…...
Git标签管理：从基础到高阶自动化实践
引言 在软件发布过程中，88%的生产事故与版本标记错误相关。Git标签（Tag）作为版本控制的关键锚点，不仅是发布流程的里程碑，更是代码审计和问题追溯的重要依据。本文将深入Git标签的底层机制，揭示企业级标签…...
运行Petalinux的准备
参考文档 建议使用Xilinx官方的文档中心DocNav，在Design Hub View选项卡中可以看到Xilinx官方组织的开发流程，非常详尽且总是最新的。 《UG1144-petalinux-tools-reference-guide》 安装linux系统 1.查看Petalinux版本支持的系统版本,对于官方未提及或…...
Jenkins 通过 Execute Shell 执行 shell 脚本 七
Jenkins 通过 Execute Shell 执行 shell 脚本 七 一、创建 .sh 文件 项目目录下新建 .sh 文件 jenkins-script\shell\ci_android_master.sh添加 Execute Shell 模块 在 Command 中添加 # 获取 .sh 路径 CI_ANDROID_MASTER_PATH"${WORKSPACE}/jenkins-script/shell/…...
AT32系列微控制器低压电机控制开发板
参考：《UM0014_AT32_LV_Motor_Control_EVB_V20_User_Manual_V1.0.1_ZH.pdf》 开发板介绍 此电机开发板是一个泛用型的低压三相电机驱动器，应用雅特力科技AT32系列微控制器搭配雅特力电机函数库，可驱动直流无刷电机、交流同步电机࿰…...
k8s部署redis集群
前置环境：已部署k8s集群，ip地址为 192.168.10.1~192.168.10.5，总共5台机器。 1. 创建provisioner制备器（如果已存在，则不需要） 需要部署方式，可以参考我之前的文章：k8s部署rabbitmq-CSDN博客 2. 新增redis配置文件 redis-6001.yaml --- apiVersion: v1 kind: Serv…...
道路运输安全员考试题库及答案
一、判断题 32.驾驶员必须取得道路危险货物运输从业资格证，才能从事道路危险货物运输活动。 答案：正确 33.可以将危险货物与普通货物混装运输。 答案：错误 34.货车正常行驶时，转向轮转向后应有一定的回正能力，以使货…...
反射概率以及一些基本API的使用
请问，获取对象有几种方式？ 1、通过构造函数来new一个对象； 2、通过clone来克隆一个对象； 3、通过序列化反序列化来构建一个对象； 4、通过反射来创建对象；a、通过Class类来创建；b、通过Const…...
DeepSeek API 调用 - Spring Boot 实现
DeepSeek API 调用 - Spring Boot 实现 1. 项目依赖 在 pom.xml 中添加以下依赖： <dependencies><dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-webflux</artifactId></depe…...
机器学习 - 理论和定理
在机器学习中，有一些非常有名的理论或定理，对理解机器学习的内在特性非常有帮助。本文列出机器学习中常用的理论和定理，并举出对应的举例子加以深化理解，有些理论比较抽象，我们可以先记录下来，慢慢啃&#…...
Java进阶：Docker
1. Docker概述 1.1. Docker简介 Docker 是一个开源的应用容器引擎，基于 Go 语言开发。Docker 可以让开发者打包他们的应用以及依赖包到一个轻量级、可移植的容器中，然后发布到任何流行的 Linux 机器上，也可以实现虚拟化。容器是完全使用沙箱…...
Winform禁止高分辨下缩放布局成功方法
Windows自动缩放布局会导致窗体上的按钮和文本挤在一起根本看不清楚。 那么该如何解决呢？ 具体操作步骤如下： 1、在项目属性上切换到【安全性】菜单，勾选【启用ClickOnce安全设置】，然后立刻取消勾选； 为了生成app.…...
力扣142题——环形链表II
#题目# #代码# #链接# 这道链表题还是需要一些思维，这里把代码随想录的链接也贴在这里，有需要的小伙伴自行点击： https://programmercarl.com/0142.%E7%8E%AF%E5%BD%A2%E9%93%BE%E8%A1%A8II.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%…...
工厂设计模式
工厂设计模式 简介 工厂模式是一种创建型设计模式，用于创建产品，代替手动new，主要包括简单工厂模式、工厂方法模式、抽象工厂模式。 一、简单工厂模式 定义：通过一个工厂类根据传入的参数匹配创建的产品 结构组成：…...
网络安全之探险
因为工作相关性，看着第三方公司出具的网络安全和shentou测试报告就想更深入研究一下，于是乎开始探索网络安全方面的知识，度娘、知乎开始一步步开始，总结昨天学到皮毛知识。 1.考证大全，开始是奔着这个目的去的 2.有用…...
Python基础语法精要
文章目录 一、Python的起源二、Python的用途三、Python的优缺点优点缺点 四、基础语法（1）常量和表达式（2）变量变量的语法（i）定义变量（ii）变量命名的规则 （3）变…...
C语言（枚举类型）
目录 1、什么是枚举 2、枚举成员的类型 3、枚举类型的实际应用 1、什么是枚举 枚举的定义就是：枚举（Enumeration）是一种用户自定义的数据类型，用于定义一组具有离散值的符号常量。 那通俗一点说就是把一些固定的值，一…...
讯方·智汇云校华为授权培训机构的介绍
官方授权 华为授权培训服务伙伴（Huawei Authorized Learning Partner，简称HALP）是获得华为授权，面向公众（主要为华为企业业务的伙伴/客户）提供与华为产品和技术相关的培训服务，培养华为产业链所…...
高级 Conda 使用：环境导出、共享与优化
1. 引言 在 Conda 的基础包管理功能中，我们了解了如何安装、更新和卸载包。但对于开发者来说，如何更好地管理环境、导出环境配置、共享环境，以及如何优化 Conda 的使用效率，才是提高工作效率的关键。本篇博客将进一步深入 Conda …...
从算法到落地：DeepSeek如何突破AI工具的同质化竞争困局
🎁个人主页：我们的五年 🔍系列专栏：Linux网络编程 🌷追光的人，终会万丈光芒 🎉欢迎大家点赞👍评论📝收藏⭐文章 Linux网络编程笔记： https://blog.cs…...
P9584 「MXOI Round 1」城市
题目描述 小 C 是 F 国的总统，尽管这个国家仅存在于网络游戏中，但他确实是这个国家的总统。 F 国由 n 个城市构成，这 n 个城市之间由 n−1 条双向道路互相连接。保证从任意一个城市出发，都能通过这 n−1 条双向道路，…...
CodeGPT + IDEA + DeepSeek，在IDEA中引入DeepSeek实现AI智能开发
CodeGPT IDEA DeepSeek，在IDEA中引入DeepSeek 版本说明 建议和我使用相同版本，实测2022版IDEA无法获取到CodeGPT最新版插件。（在IDEA自带插件市场中搜不到，可以去官网搜索最新版本） ToolsVersionIntelliJ IDEA202…...
Filter过滤器
Filter:过滤器 概念： web中的过滤器：当访问服务器的资源时，过滤器可以将请求拦截下来，完成一些特殊的功能 过滤器的作用：一般用于完成通用的操作。如：登录验证、统一编码处理、敏感字符处理… 过滤器的生…...
git如何下载指定版本
要使用Git下载指定版本，可以通过以下步骤进行操作： 1. 使用Git命令行下载指定版本： 1.1 首先，使用git clone命令克隆整个git库到本地。例如：git clone [库的URL]。这将下载最新的代码到本地。 1.2 进入克隆…...
开源的 DeepSeek-R1「GitHub 热点速览」
春节假期回来，一睁眼全是王炸级的开源模型 DeepSeek-R1！ GitHub 地址→github.com/deepseek-ai/DeepSeek-R1 DeepSeek-R1 开源还不到一个月，Star 数就飙升至冲破天际的 70k。虽然目前仅开源了模型权重，但同时发布的技术论文详细地…...
Open FPV VTX开源之OSD使用分类
Open FPV VTX开源之OSD使用分类 1. 源由2. 硬件2.1 【天空端】SigmaStar2.2 【天空端】Raspberry Pi2.3 【地面端】 3. 软件3.1 天空端软件3.2 地面端软件 4. 分类4.1 嵌入式OSD分类A1-嵌入式OSD：SigmaStar Android分类A2-嵌入式OSD：SigmaStar Hi3536分…...