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

LeetCode 热题 100 114. 二叉树展开为链表

LeetCode 热题 100 | 114. 二叉树展开为链表

大家好,今天我们来解决一道经典的二叉树问题——二叉树展开为链表。这道题在 LeetCode 上被标记为中等难度,要求将二叉树展开为一个单链表,展开后的单链表应该与二叉树的先序遍历顺序相同。


问题描述

给你二叉树的根结点 root,请你将它展开为一个单链表:

  • 展开后的单链表应该同样使用 TreeNode,其中 right 子指针指向链表中下一个结点,而左子指针始终为 null
  • 展开后的单链表应该与二叉树先序遍历顺序相同。

示例 1:

输入:root = [1,2,5,3,4,null,6]
输出:[1,null,2,null,3,null,4,null,5,null,6]

示例 2:

输入:root = []
输出:[]

示例 3:

输入:root = [0]
输出:[0]

提示:

  • 树中结点数在范围 [0, 2000]
  • -100 <= Node.val <= 100

解题思路

核心思想
  1. 递归展开

    • 使用递归方法,先序遍历二叉树,将每个节点的左子树和右子树展开为链表。
    • 将左子树的链表连接到当前节点的右子树上,然后将右子树的链表连接到左子树链表的末尾。
  2. 原地展开

    • 通过递归调用,原地修改节点的指针,避免使用额外的空间。

Python代码实现

class Solution:def flatten(self, root: TreeNode) -> None:"""Do not return anything, modify root in-place instead."""def flatten_tree(node):if not node:return None# 递归展开左子树和右子树left_tail = flatten_tree(node.left)right_tail = flatten_tree(node.right)# 如果有左子树,将其连接到右子树的位置if left_tail:left_tail.right = node.rightnode.right = node.leftnode.left = None# 返回当前子树的尾节点return right_tail or left_tail or nodeflatten_tree(root)

代码解析

  1. 递归函数

    • 定义一个递归函数 flatten_tree,用于展开以某个节点为根的子树。
    • 如果当前节点为空,返回 None
  2. 递归展开左右子树

    • 递归调用 flatten_tree,分别展开当前节点的左子树和右子树,返回左子树和右子树的尾节点。
  3. 连接左子树和右子树

    • 如果左子树不为空,将左子树的尾节点连接到右子树的头节点。
    • 将当前节点的右子树指向左子树的头节点。
    • 将当前节点的左子树设置为 None
  4. 返回尾节点

    • 返回当前子树的尾节点,用于连接后续的子树。
  5. 主函数

    • 调用 flatten_tree(root),从根节点开始展开整个二叉树。

复杂度分析

  • 时间复杂度:O(n),其中 n 是二叉树的节点数。每个节点恰好被访问一次。
  • 空间复杂度:O(log n),递归调用栈的深度最多为树的高度,对于平衡树为 O(log n),对于非平衡树可能达到 O(n)。

示例运行

示例 1
输入:root = [1,2,5,3,4,null,6]
输出:[1,null,2,null,3,null,4,null,5,null,6]
示例 2
输入:root = []
输出:[]
示例 3
输入:root = [0]
输出:[0]

总结

通过递归方法,我们可以高效地将二叉树展开为单链表。递归展开左右子树,并将左子树连接到右子树的位置,最终实现原地展开。希望这篇题解对大家有所帮助,如果有任何问题,欢迎在评论区留言讨论!

关注我,获取更多算法题解和编程技巧!

相关文章:

LeetCode 热题 100 114. 二叉树展开为链表

LeetCode 热题 100 | 114. 二叉树展开为链表 大家好&#xff0c;今天我们来解决一道经典的二叉树问题——二叉树展开为链表。这道题在 LeetCode 上被标记为中等难度&#xff0c;要求将二叉树展开为一个单链表&#xff0c;展开后的单链表应该与二叉树的先序遍历顺序相同。 问题…...

DML和DQL

1. 设置MySQL的储存引擎 上一章的附录里已经将ini设置好了&#xff0c;不用再次设置 2. DML语句 插入单数据记录 插入多数据记录 将查询结果插入新表 更新数据 删除数据 注意&#xff1a;delete删除只会删除数据&#xff0c;不会重置表的现有逻辑&#xff0c;truncate会重置表逻…...

多线程与线程互斥

我们初步学习完线程之后&#xff0c;就要来试着写一写多线程了。在写之前&#xff0c;我们需要继续来学习一个线程接口——叫做线程分离。 默认情况下&#xff0c;新创建的线程是joinable的&#xff0c;线程退出后&#xff0c;需要对其进行pthread_join操作&#xff0c;否则无法…...

BMS工具箱用来执行贝叶斯模型平均(BMA)计算模块

贝叶斯模型平均&#xff08;Bayesian Model Averaging&#xff0c;BMA&#xff09;是一种用于处理模型不确定性的统计方法&#xff0c;通过结合多个模型的预测结果来提高预测的准确性和鲁棒性。在 MATLAB 中&#xff0c;可以使用专门的工具箱&#xff08;如 BMS 工具箱&#xf…...

Java死锁排查:线上救火实战指南

想象一下&#xff0c;你正在值班&#xff0c;突然监控告警红成一片&#xff0c;用户反馈雪花般飘来&#xff1a;“系统卡死了&#xff01;用不了了&#xff01;” —— 这很可能就是Java应用遭遇了“死锁”这个大魔王。这时候&#xff0c;你就是救火队长&#xff0c;首要任务不…...

第十九次博客打卡

今天学习的内容是Java中的常见循环。 在 Java 中&#xff0c;常见的循环结构主要有以下几种&#xff1a;for 循环、while 循环、do-while 循环以及增强型 for 循环&#xff08;也称为 for-each 循环&#xff09;。 1. for 循环 for 循环是一种非常灵活的循环结构&#xff0c…...

智能体制作学习笔记1——智能体

01 智能体_哔哩哔哩_bilibili 大语言模型可以理解成一个很厉害的人。 但是要完成一些特定的工作&#xff0c;除了大语言模型&#xff0c;还需要一些工具和业务流程&#xff0c;这样才能自动化帮我们完成特定的工作&#xff0c;这个就叫做智能体。 突然发现放视频的时候出现了…...

Python常见问题

文章目录 1.python有哪些数据类型2.python中的元组和列表的区别是什么&#xff1f;3.python中的break、continue、pass代表什么意思&#xff1f;4.如何在python中生成一个随机数&#xff1f;5.Python有哪些常见的内置函数&#xff1f;6.请用自己最擅长的编程语言&#xff0c;将…...

小程序 存存上下滑动的页面

推荐阅读文档&#xff1a; Vue3组合式API之getCurrentInstance详解 - 且行且思 - 博客园Vue2中&#xff0c;可以通过this来获取当前组件实例&#xff1b; Vue3中&#xff0c;在setup中无法通过this获取组件实例&#xff0c;console.log(this)打印出来的值是undefined。 在Vue3…...

更换git位置并在pycharm中重新配置

更新 PyCharm 中的 Git 路径 更新 PyCharm 终端的 Shell 路径 检查环境变量 确保系统环境变量中的 Path 包含了新的 Git 安装路径 &#xff0c;如果使用unins0000自动卸载就不会有旧路径。...

AI世界的崩塌:当人类思考枯竭引发数据生态链断裂

AI世界的崩塌&#xff1a;当人类思考枯竭引发数据生态链断裂 ——论过度依赖AI创作对技术进化的反噬 一、数据生态的恶性循环&#xff1a;AI的“自噬危机” 当前AI模型的训练依赖于人类创造的原始数据——书籍、论文、艺术作品、社交媒体动态等。据统计&#xff0c;2025年全球…...

OkHttp连接池

&#x1f9f0; 调整连接池的核心参数 ✅ 最大空闲连接数&#xff08;maxIdleConnections&#xff09;&#xff1a; 含义&#xff1a;连接池中最多保留的空闲连接数量。默认值&#xff1a;5建议值&#xff1a;10~50&#xff08;视并发量而定&#xff09; ✅ 连接保持时间&…...

哈希表的实现01

文章目录 哈希表的实现01哈希概念直接定址法哈希冲突负载因子将关键字转换为整数 哈希函数除法散列法&#xff1a;乘法散列法&#xff08;了解&#xff09;全域散列法&#xff08;了解&#xff09; 处理哈希冲突&#xff08;开放定址法&#xff09;线性探测&#xff1a;二次探测…...

学习日志06 java

还有四天要去比赛了&#xff0c;能赢吗&#xff1f;逼自己一把。。。&#xff01;&#xff01;加油&#xff01; 1 对比一下java重写还是不重写tostring的区别 1. 不重写 toString() 的情况 java class Point {private int x;private int y;public Point(int x, int y) {th…...

spring中的@MapperScan注解详解

一、核心功能与作用 MapperScan是Spring与MyBatis框架集成时用于批量扫描Mapper接口的核心注解&#xff0c;其主要功能包括&#xff1a; 自动注册Mapper接口 通过指定包路径&#xff0c;Spring会自动扫描该路径下的所有Mapper接口&#xff0c;并将其注册为Spring Bean&#x…...

PYTHON训练营DAY25

BUG与报错 一、try else try:# 可能会引发异常的代码 except ExceptionType: # 最好指定具体的异常类型&#xff0c;例如 ZeroDivisionError, FileNotFoundError# 当 try 块中发生 ExceptionType 类型的异常时执行的代码 except: # 不推荐&#xff1a;捕获所有类型的异常&…...

视频图像压缩领域中 DCT 的 DC 系数和 AC 系数详解

引言 在数字图像与视频压缩领域&#xff0c;离散余弦变换&#xff08;Discrete Cosine Transform, DCT&#xff09;凭借其卓越的能量集中特性&#xff0c;成为JPEG、MPEG等国际标准的核心技术。DCT通过将空域信号映射到频域&#xff0c;分离出DC系数&#xff08;直流分量&…...

YOLO v1:目标检测领域的革命性突破

引言 在计算机视觉领域&#xff0c;目标检测一直是一个核心任务&#xff0c;它不仅要识别图像中的物体类别&#xff0c;还要确定物体的精确位置。传统目标检测方法如R-CNN系列虽然准确率高&#xff0c;但计算复杂度高、速度慢。2016年&#xff0c;Joseph Redmon等人提出的YOLO…...

AI智能体 | 使用Coze一键制作“假如书籍会说话”视频,18个作品狂吸17.6万粉,读书博主新标杆!(附保姆级教程)

目录 一、整体工作流设计 二、制作工作流 2.1 开始节点 2.2 大模型_生成对话文案 2.3 代码_字幕切割 2.4 画板_对话背景 2.5 循环_对话语音01 2.5.1 选择器_2 2.5.2 语音合成02 2.5.3 语音合成03 2.5.4 变量聚合_1 2.5.5 视频合成01 2.6 循环_3 2.6.1 选择器_3 …...

HVV蓝队实战面试题

HVV蓝队实战&#xff0c;防守筹备之“部署蜜罐捕获横向扫描行为”。 蜜罐通过模拟内网脆弱服务&#xff08;如SMB、SSH、数据库端口&#xff09;&#xff0c;诱捕攻击者突破边界后的横向探测行为。 通过监测高频端口扫描、非常规协议请求及非授权IP段遍历&#xff0c;结合多源…...

正则表达式(二)-高级应用_谨慎使用

没事建议别瞎用正则表达式,能让后端处理好的数据,尽量后端处理好,减少前端对数据的处理,保证数据原始的完整性,减少前端耗能。(其实就是懒╮(╯▽╰)╭) 1. 分组捕获 分组捕获用于提取匹配的子字符串,使用 () 定义分组。 示例:提取日期中的年、月、日 (\d{4})-(\d{2…...

在K8S集群中部署EFK日志收集

目录 引言环境准备安装自定义资源部署ElasticsearchMaster 节点与 Data 节点的区别生产优化建议安装好以后测试ES是否正常部署Fluentd测试filebeat是否正常推送日志部署Kibana获取账号密码&#xff0c;账号是&#xff1a;elastic集群测试 引言 系统版本为 Centos7.9内核版本为…...

解决常见数据库问题:保障数据安全与稳定的全方位指南

本文结合行业最佳实践与前沿技术&#xff0c;系统性总结数据库运维中的核心问题与解决方案&#xff0c;助力开发者构建高可靠、高性能的数据服务&#xff09; 一、性能优化&#xff1a;从SQL到架构的全面调优 性能问题是数据库运维中最常见的挑战&#xff0c;直接影响用户体验…...

武汉科技大学人工智能与演化计算实验室许志伟课题组参加2025中国膜计算论坛

武汉科技大学人工智能与演化计算实验室许志伟课题组参加2025中国膜计算论坛 2025年5月9日至11日&#xff0c;第五届中国膜计算论坛&#xff08;CWMC 2025&#xff09;在成都信息工程大学隆重召开。会议由 国际膜计算学会&#xff08;IMCS&#xff09; 主办&#xff0c;汇聚了来…...

Femap许可硬件绑定

在电磁仿真领域&#xff0c;Femap软件因其卓越的性能和广泛的应用场景而备受用户青睐。为了确保软件的安全与稳定运行&#xff0c;Femap提供了许可硬件绑定的功能。本文将详细介绍Femap许可硬件绑定的概念和优势&#xff0c;帮助您了解并充分利用这一功能&#xff0c;确保软件在…...

构建优雅对象的艺术:Java 建造者模式的架构解析与工程实践

一、建造者模式的本质与核心价值 在面向对象的软件设计中&#xff0c;创建复杂对象一直是一个需要精心处理的问题。当一个对象的构建需要多个步骤&#xff0c;并且这些步骤具有不同的组合方式时&#xff0c;传统的构造函数方式会显得力不从心。建造者模式&#xff08;Builder …...

vim启动的时候,执行gg

在 Vim 编辑器中&#xff0c;gg 命令是一个非常有用的命令&#xff0c;它可以将光标快速移动到当前窗口的顶部&#xff08;即第一行&#xff09;。如果你想在 Vim 启动时自动执行 gg 命令&#xff0c;有几种方法可以实现这一点&#xff1a; 方法 1&#xff1a;使用 Vim 的启动…...

【SSL部署与优化​】​​HTTP/2与HTTPS的协同效应

HTTP/2与HTTPS的协同效应&#xff1a;为何HTTP/2强制要求TLS 1.2&#xff1f; HTTP/2是HTTP协议的现代升级版&#xff0c;旨在通过多路复用、头部压缩等技术提升性能。然而&#xff0c;HTTP/2的设计与部署与HTTPS&#xff08;TLS加密&#xff09;紧密相关&#xff0c;甚至强制…...

JavaScript篇:揭秘函数式与命令式编程的思维碰撞

大家好&#xff0c;我是江城开朗的豌豆&#xff0c;一名拥有6年以上前端开发经验的工程师。我精通HTML、CSS、JavaScript等基础前端技术&#xff0c;并深入掌握Vue、React、Uniapp、Flutter等主流框架&#xff0c;能够高效解决各类前端开发问题。在我的技术栈中&#xff0c;除了…...

ubuntu24.04上安装NVIDIA driver+CUDA+cuDNN+Anaconda+Pytorch

一、NVIDIA driver 使用Ubuntu系统的&#xff1a;软件和更新——>附加驱动&#xff0c;安装NVIDIA驱动。 二、CUDA 安装命令&#xff1a;sudo apt install nvidia-cuda-toolkit 三、cuDNN cuDNN 9.10.0 Downloads | NVIDIA Developer 四、Anaconda Download Anaconda Di…...

vue3基础学习(上) [简单标签] (vscode)

目录 1. Vue简介 2. 创建Vue应用 2.1 下载JS文件 2.2 引用JS文件 2.3 调用Vue方法​编辑 2.4 运行一下试试: 2.5 代码如下 3.模块化开发模式 3.1 Live Server插件 3.2 运行 4. 常用的标签 4.1 reactive 4.1.1 运行结果 4.1.2 代码: 4.2 ref 4.2.1 运行结果 4.2.2…...

.Net HttpClient 使用代理功能

HttpClient 使用代理功能 实际开发中&#xff0c;HttpClient 通过代理访问目标服务器是常见的需求。 本文将全面介绍如何在 .NET 中配置 HttpClient 使用代理&#xff08;Proxy&#xff09;功能&#xff0c;包括基础使用方式、代码示例、以及与依赖注入结合的最佳实践。 注意…...

深入理解Java适配器模式:从接口兼容到设计哲学

引言&#xff1a;接口不兼容的困局 在软件开发中&#xff0c;我们经常遇到这样的场景&#xff1a; 旧系统有一个「RS232串口设备」&#xff08;仅支持sendByRS232(String data)方法&#xff09;&#xff0c;新系统需要通过「USB接口」&#xff08;要求sendByUSB(String data)…...

非异步信号安全函数

这个程序演示了如何使用sigaction来捕获和处理信号&#xff08;特别是SIGINT&#xff0c;即CtrlC&#xff09;。以下是关键点和潜在问题的分析&#xff1a; 程序功能 信号捕获&#xff1a;注册自定义处理函数handler来捕获信号2&#xff08;SIGINT&#xff0c;通常由CtrlC触发…...

PHP黑白胶卷底片图转彩图功能 V2025.05.15

关于底片转彩图 传统照片底片是摄影过程中生成的反色图像&#xff0c;为了欣赏照片&#xff0c;需要通过冲印过程将底片转化为正像。而随着数字技术的发展&#xff0c;我们现在可以使用数字工具不仅将底片转为正像&#xff0c;还可以添加色彩&#xff0c;重现照片原本的色彩效…...

【C++ / STL】封装红黑树实现map和set

文章目录 一. 源码及框架分析1.决定搜索类型的传参思考&#xff1a;为什么要传第一个参数 2.KeyOfValue的作用 二. 模拟实现map和set1. 实现出复用红黑树框架,并支持insert2. 支持iterator的实现iterator实现思路分析【iterator操作实现详解】 3.支持map的[ ]操作4.map和set代码…...

记录: Windows下远程Liunx 系统xrdp 用到的一些小问题(免费踩坑 记录)

采用liunx Ubuntu22.04版本以下&#xff0c;需要安装 xrdp 或者VNC 具体过程就是下载 在linux命令行里 首先更新软件包&#xff1a;sudo apt update 安装xrdp服务&#xff1a;sudo apt install xrdp 启动XRDP&#xff1a;sudo systemctl start xrdp&#xff08;如果在启动的…...

WordPress 文章和页面:它们的区别是什么?

很多刚接触WordPress的用户&#xff0c;在创建网站内容时往往会遇到这样一个问题&#xff1a;“我应该用‘文章’还是‘页面’&#xff1f;”虽然两者都能发布内容&#xff0c;但它们之间到底有什么区别呢&#xff1f;这篇文章将从易于理解的角度&#xff0c;帮助大家厘清WordP…...

【工具变量】各省市场化指数-杨兴权版共三个方法(1997-2023年)

市场化指数是衡量中国各地区市场化改革进程的重要指标。本次数据基于杨兴全、马连福和夏立军三位学者的研究成果&#xff0c;系统整理并更新了我国1997-2023年间31个省、自治区、直辖市的市场化指数&#xff0c;便于研究者进行横向和纵向比较分析。 一、数据介绍 数据名称&…...

Android App View——团结引擎车机版实现安卓应用原生嵌入 3D 开发场景

团结引擎 1.5.0 版本已于 4 月 14 日正式发布&#xff0c;从 1.5.0 版本开始&#xff0c;团结引擎车机版带来了一个激动人心的新能力 —— Android App View。现在&#xff0c;开发者可以将任意第三方安卓应用以 2D 组件或 3D 组件的形式&#xff0c;原生嵌入到 Tuanjie 开发的…...

完整的 CentOS 6.10 虚拟机安装启动脚本

好的&#xff01;下面是一个 完整的 CentOS 6.10 虚拟机安装启动脚本&#xff0c;专为你在 macOS&#xff08;M 系芯片&#xff09; QEMU&#xff08;x86_64 软件模拟&#xff09; 环境设计&#xff0c;确保你能顺利启动并安装一个接近 Red Hat 6.4 的开发环境。 ⸻ ✅ 前提准…...

如何远程执行脚本不留痕迹

通常我们在做远程维护的时候&#xff0c;会有这么一个需求&#xff0c;就是我想在远程主机执行一个脚本&#xff0c;但是这个脚本我又不想保留在远程主机上&#xff0c;那么有人就说了&#xff0c;那就复制过去再登录远程执行不就行了吗&#xff1f;嗯嗯&#xff0c;但是这还不…...

观测云:从云时代走向AI时代

过去十年&#xff0c;云计算让企业的数据处理能力实现了指数级增长&#xff0c;而观测云作为全栈监控观测平台&#xff0c;见证并参与了这一进程。通过强大的数据采集、处理与展示能力&#xff0c;观测云帮助数百家企业实现了对 IT 基础设施、应用服务、业务链路的全面掌控。 …...

解密企业级大模型智能体Agentic AI 关键技术:MCP、A2A、Reasoning LLMs- consistency is the key

解密企业级大模型智能体Agentic AI 关键技术&#xff1a;MCP、A2A、Reasoning LLMs- consistency is the key DeepSeek v3的时候&#xff0c;它模型已经足够强大到能带来consistency稳定性。所以当这个DeepSeek R1 Zero或者DeepSeek R1使用GRPO进行训练的时候&#xff0c;它能够…...

鸿蒙OSUniApp 实现图片上传与压缩功能#三方框架 #Uniapp

UniApp 实现图片上传与压缩功能 前言 在移动应用开发中&#xff0c;图片上传是一个非常常见的需求。无论是用户头像、朋友圈图片还是商品图片&#xff0c;都需要上传到服务器。但移动设备拍摄的图片往往尺寸较大&#xff0c;直接上传会导致流量消耗过大、上传时间过长&#x…...

SymPy | 如何提取指定项的系数

SymPy 是 Python 中一个强大的符号计算库&#xff0c;广泛应用于数学、物理和工程领域的符号运算。在代数表达式的处理中&#xff0c;提取特定项的系数是一项常见且重要的操作。本文将详细介绍 SymPy 中提取指定项系数的多种方法&#xff0c;并通过丰富的示例帮助读者掌握这些技…...

MUSE Pi Pro 更换kernel内核及module模块

视频讲解&#xff1a; MUSE Pi Pro 更换kernel内核及module模块 脚本仓库&#xff1a; https://github.com/LitchiCheng/MUSE-Pi-Pro-Learning 结合上期编译内核&#xff0c;编译成功后的输出如下&#xff1a; 输入 uname -a 可以看到如下信息&#xff0c;未修改的内核时间在 …...

java每日精进 5.14【参数校验】

参数校验 1.1概述 本文使用 Hibernate Validator 框架对 RESTful API 接口的参数进行校验&#xff0c;确保数据入库的正确性。 例如&#xff0c;在用户注册时&#xff0c;校验手机号格式、密码强度等。如果校验失败&#xff0c;抛出 ConstraintViolationException 或相关异…...

CPS联盟+小程序聚合平台分销返利系统开发|小红书番茄网盘CPA拉新推广全解析

导语&#xff1a; 在私域流量与社交电商爆发的时代&#xff0c;CPS联盟分销返利系统与小红书CPA拉新推广成为企业增长的核心引擎。本文深度解析如何通过小程序聚合平台开发、多层级返利机制搭建及精准CPA推广策略&#xff0c;快速占领市场&#xff0c;实现用户裂变与收益倍增。…...

基于EFISH-SCB-RK3576/SAIL-RK3576的光伏逆变器控制器技术方案

&#xff08;国产化替代J1900的能源物联网解决方案&#xff09; 一、硬件架构设计‌ ‌电力转换与控制模块‌ ‌高精度功率控制‌&#xff1a; Cortex-M0硬实时核驱动多相PWM&#xff08;频率>200kHz&#xff09;&#xff0c;动态调节DC-AC转换误差<0.5%FPGA实现MPPT算法…...