当前位置: 首页 > news >正文

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 二叉树展开为链表

代码思路 目标&#xff1a; 将二叉树展平&#xff08;flatten&#xff09;为一个单链表。展平后的链表应该按照前序遍历的顺序排列节点&#xff0c;即&#xff1a; • 节点的左子树指针设置为 nullptr。 • 节点的右子树指针指向下一个节点。 代码注释及思路 class Solution…...

2.14学习总结

#include <stdio.h> #include <stdlib.h> #include <math.h>#define MAX_N 32767// 二分查找最接近目标值的元素 int binarySearch(int* arr, int left, int right, int target) {while (left < right) {int mid left (right - left) / 2;if (arr[mid] …...

在WPS中通过JavaScript宏(JSA)调用本地DeepSeek API优化文档教程

既然我们已经在本地部署了DeepSeek,肯定希望能够利用本地的模型对自己软件开发、办公文档进行优化使用,接下来就先在WPS中通过JavaScript宏(JSA)调用本地DeepSeek API优化文档的教程奉上。 前提: (1)已经部署好了DeepSeek,可以看我的文章:个人windows电脑上安装DeepSe…...

zola + github page,用 workflows 部署

之前的Zola都是本地build之后&#xff0c;再push到github上&#xff0c;这种方式很明显的弊端就是只能在本地编辑&#xff0c;而不能通过github编辑&#xff0c;再pull到本地&#xff0c;缺乏了灵活性。因此将zola用workflows来部署。 repo地址&#xff1a;https://github.com/…...

【科技革命】颠覆性力量与社会伦理的再平衡

目录 2025年科技革命&#xff1a;颠覆性力量与社会伦理的再平衡目录技术突破全景图认知智能的范式转移量子霸权实现路径生物编程技术革命能源结构重构工程 产业生态链重构医疗健康新范式教育系统智能进化金融基础设施变革制造范式革命 科技伦理与文明演进 2025年科技革命&#…...

UIView 与 CALayer 的联系和区别

今天说一下UIView 与 CALayer 一、UIView 和 CALayer 的关系 在 iOS 开发中&#xff0c;UIView 是用户界面的基础&#xff0c;它负责处理用户交互和绘制内容&#xff0c;而 CALayer 是 UIView 内部用于显示内容的核心图层&#xff08;Layer&#xff09;。每个 UIView 内部都有…...

Jenkins 新建配置 Freestyle project 任务 六

Jenkins 新建配置 Freestyle project 任务 六 一、新建任务 在 Jenkins 界面 点击 New Item 点击 Apply 点击 Save 回到任务主界面 二、General 点击左侧 Configure Description&#xff1a;任务描述 勾选 Discard old builds Discard old builds&#xff1a;控制何时…...

深入解析A2DP v1.4协议:蓝牙高质量音频传输的技术与实现

1. A2DP概述 A2DP&#xff08;Advanced Audio Distribution Profile&#xff09;是一种高质量音频流媒体协议&#xff0c;旨在实现高质量音频内容的分发&#xff0c;通常用于通过蓝牙设备传输音频数据&#xff0c;例如将音乐从便携式播放器传输到耳机或扬声器。与传统的蓝牙语…...

mybatis-plus逆向code generator pgsql实践

mybatis-plus逆向code generator pgsql实践 环境准备重要工具的版本供参考pom依赖待逆向的SQL 配置文件CodeGenerator配置类配置类说明 环境准备 重要工具的版本 jdk1.8.0_131springboot 2.7.6mybatis-plus 3.5.7pgsql 14.15 供参考pom依赖 <?xml version"1.0&quo…...

Android Studio:RxBus结合ICompositeSubscription使用

我现在想用 RxBus 来发布和订阅事件&#xff0c;同时使用 ICompositeSubscription 来管理订阅。跟前一个博客的区别在于&#xff0c;事件流的产生方式不同&#xff0c;更加得全面。 目标 使用 RxBus 发布事件。使用 ICompositeSubscription 来管理订阅。在 Activity 中创建订…...

微软AutoGen高级功能——Magentic-One

介绍 大家好&#xff0c;博主又来给大家分享知识了&#xff0c;这次给大家分享的内容是微软AutoGen框架的高级功能Magentic-One。那么它是用来做什么的或它又是什么功能呢&#xff0c;我们直接进入正题。 Magentic-One Magnetic-One是一个通用型多智能体系统&#xff0c;用于…...

redis cluster测试

集群节点信息这时候停掉一个master 172.30.60.31 从集群信息集中我们可以看到172.30.60.31的slave是172.30.60.41&#xff0c;查看41的日志&#xff0c;发现他成为了新的master 这时候我们在将172.30.60.41也杀死&#xff0c;会发现集群异常了 尝试把172.30.60.31启动&#xff…...

【ARM】JTAG接口介绍

1、 文档目标 对 JTAG 接口有更多的认识&#xff0c;在遇到关于 JTAG 接口问题时有一些排查的思路。 2、 问题场景 在使用调试器过程时&#xff0c;免不了要接触到 JTAG 接口&#xff0c;当出现连接不上时&#xff0c;就不知道从哪来进行排查。 3、软硬件环境 1 软件版本&am…...

处理项目中存在多个版本的jsqlparser依赖

异常提示 Correct the classpath of your application so that it contains a single, compatible version of net.sf.jsqlparser.statement.select.SelectExpressionIte实际问题 原因&#xff1a;项目中同时使用了 mybatis-plus 和 pagehelper&#xff0c;两者都用到了 jsqlpa…...

部署 DeepSeek R1各个版本所需硬件配置清单

DeepSeek-R1 通过其卓越的推理性能和灵活的训练机制&#xff0c;在 2025 年的春节期间受到了广泛关注。 DeepSeek-R1 是一款高性能的 AI 推理模型&#xff0c;主要通过强化学习技术来增强模型在复杂任务场景下的推理能力。 在本地部署 DeepSeek-R1 时&#xff0c;尤其是完整的…...

数据结构:Map Set(一)

目录 一、搜索树 1、概念 2、查找 3、插入 4、删除 二、搜索 1、概念及场景 2、模型 &#xff08;1&#xff09;纯key模型 &#xff08;2&#xff09;Key-Value模型 三、Map的使用 1、什么是Map&#xff1f; 2、Map的常用方法 &#xff08;1&#xff09;V put(K …...

zabbix 监控系统 配置钉钉告警

步骤1&#xff1a;创建钉钉群 步骤2&#xff1a;创建机器人 点击群设置 然后下划选择机器人。 点击添加机器人 选择自定义机器人 点击添加 1、设置机器人的名字和群组 2、设置自定义关键字 zabbix 告警 报警 恢复 3、点击我已阅读并同意 4、点击完成 生成webhook 链接 注…...

跟着李沐老师学习深度学习(十一)

经典的卷积神经网络 在本次笔记中主要介绍一些经典的卷积神经网络模型&#xff0c;主要包含以下&#xff1a; LeNet&#xff1a;最早发布的卷积神经网络之一&#xff0c;目的是识别图像中的手写数字&#xff1b;AlexNet&#xff1a; 是第一个在大规模视觉竞赛中击败传统计算机…...

32单片机学习记录4之串口通信

32单片机学习记录4之串口通信 前置 STM32的GPIO口有通用模式&#xff0c;复用模式&#xff0c;模拟模式三种&#xff0c;加上输入输出就是有6中对应的模式。 我学习了通用模式&#xff0c;会使用GPIO口使用一些简单外设&#xff0c;如LED&#xff0c;独立按键&#xff0c;红外…...

微信小程序 - 组件和样式

组件和样式介绍 在开 Web 网站的时候&#xff1a; 页面的结构由 HTML 进行编写&#xff0c;例如&#xff1a;经常会用到 div、p、 span、img、a 等标签 页面的样式由 CSS 进行编写&#xff0c;例如&#xff1a;经常会采用 .class 、#id 、element 等选择器 但在小程序中不能…...

逻辑回归:给不确定性划界的分类大师

想象你是一名医生。面对患者的检查报告&#xff08;肿瘤大小、血液指标&#xff09;&#xff0c;你需要做出一个**决定性判断**&#xff1a;恶性还是良性&#xff1f;这种“非黑即白”的抉择&#xff0c;正是**逻辑回归&#xff08;Logistic Regression&#xff09;** 的战场&a…...

大型活动交通拥堵治理的视觉算法应用

大型活动下智慧交通的视觉分析应用 一、背景与挑战 大型活动&#xff08;如演唱会、马拉松赛事、高考中考等&#xff09;期间&#xff0c;城市交通面临瞬时人流车流激增、传统摄像头模糊、交通拥堵识别滞后等问题。以演唱会为例&#xff0c;暖城商圈曾因观众集中离场导致周边…...

(二)原型模式

原型的功能是将一个已经存在的对象作为源目标,其余对象都是通过这个源目标创建。发挥复制的作用就是原型模式的核心思想。 一、源型模式的定义 原型模式是指第二次创建对象可以通过复制已经存在的原型对象来实现,忽略对象创建过程中的其它细节。 📌 核心特点: 避免重复初…...

【git】把本地更改提交远程新分支feature_g

创建并切换新分支 git checkout -b feature_g 添加并提交更改 git add . git commit -m “实现图片上传功能” 推送到远程 git push -u origin feature_g...

LINUX 69 FTP 客服管理系统 man 5 /etc/vsftpd/vsftpd.conf

FTP 客服管理系统 实现kefu123登录&#xff0c;不允许匿名访问&#xff0c;kefu只能访问/data/kefu目录&#xff0c;不能查看其他目录 创建账号密码 useradd kefu echo 123|passwd -stdin kefu [rootcode caozx26420]# echo 123|passwd --stdin kefu 更改用户 kefu 的密码…...

[ACTF2020 新生赛]Include 1(php://filter伪协议)

题目 做法 启动靶机&#xff0c;点进去 点进去 查看URL&#xff0c;有 ?fileflag.php说明存在文件包含&#xff0c;原理是php://filter 协议 当它与包含函数结合时&#xff0c;php://filter流会被当作php文件执行。 用php://filter加编码&#xff0c;能让PHP把文件内容…...

怎么让Comfyui导出的图像不包含工作流信息,

为了数据安全&#xff0c;让Comfyui导出的图像不包含工作流信息&#xff0c;导出的图像就不会拖到comfyui中加载出来工作流。 ComfyUI的目录下node.py 直接移除 pnginfo&#xff08;推荐&#xff09;​​ 在 save_images 方法中&#xff0c;​​删除或注释掉所有与 metadata …...

关于uniapp展示PDF的解决方案

在 UniApp 的 H5 环境中使用 pdf-vue3 组件可以实现完整的 PDF 预览功能。以下是详细实现步骤和注意事项&#xff1a; 一、安装依赖 安装 pdf-vue3 和 PDF.js 核心库&#xff1a; npm install pdf-vue3 pdfjs-dist二、基本使用示例 <template><view class"con…...

【安全篇】金刚不坏之身:整合 Spring Security + JWT 实现无状态认证与授权

摘要 本文是《Spring Boot 实战派》系列的第四篇。我们将直面所有 Web 应用都无法回避的核心问题&#xff1a;安全。文章将详细阐述认证&#xff08;Authentication) 与授权&#xff08;Authorization的核心概念&#xff0c;对比传统 Session-Cookie 与现代 JWT&#xff08;JS…...

Linux安全加固:从攻防视角构建系统免疫

Linux安全加固:从攻防视角构建系统免疫 构建坚不可摧的数字堡垒 引言:攻防对抗的新纪元 在日益复杂的网络威胁环境中,Linux系统安全已从被动防御转向主动免疫。2023年全球网络安全报告显示,高级持续性威胁(APT)攻击同比增长65%,平均入侵停留时间缩短至48小时。本章将从…...