python-leetcode 45.二叉树转换为链表
题目:
给定二叉树的根节点root,请将它展开为一个单链表:
展开后的单链表应该使用同样的TreeNode,其中right子指针指向链表中的下一个节点,而左子指针始终为空
展开后的单链表应该与二叉树先序遍历顺序相同

方法一:二叉树的前序遍历
将二叉树展开为单链表之后,单链表中的节点顺序即为二叉树的前序遍历访问各节点的顺序。因此,可以对二叉树进行前序遍历,获得各节点被访问到的顺序。由于将二叉树展开为链表之后会破坏二叉树的结构,因此在前序遍历结束之后更新每个节点的左右子节点的信息,将二叉树展开为单链表。
通过递归实现前序遍历
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution(object):def flatten(self, root):""":type root: Optional[TreeNode]:rtype: None Do not return anything, modify root in-place instead."""preorderList=[]#创建一个空列表,用于存储二叉树的所有节点def preorderTraversal(root):#递归函数,用于对树进行前序遍历if root: #前序遍历的顺序是:根 -> 左 -> 右。preorderList.append(root)preorderTraversal(root.left)preorderTraversal(root.right)preorderTraversal(root)size=len(preorderList)#二叉树的节点总数for i in range(1,size): #从第二个节点开始,直到最后一个节点。因为链表的第一个节点已经由根节点 root 来表示prev,curr=preorderList[i-1],preorderList[i]#取当前节点 curr 和前一个节点 prevprev.left=None#将 prev 节点的左指针设置为 Noneprev.right=curr #将 prev 节点的右指针指向 curr
通过迭代的方式实现前序遍历
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution(object):def flatten(self, root):""":type root: Optional[TreeNode]:rtype: None Do not return anything, modify root in-place instead."""preorderList = [] # 初始化一个空列表用于存储二叉树的节点stack = [] # 初始化一个空栈用于存储遍历过程中暂时访问的节点node = root# 前序遍历二叉树while node or stack:while node:preorderList.append(node) # 将当前节点添加到列表中stack.append(node) # 将当前节点添加到栈中node = node.left # 继续遍历左子树node = stack.pop() # 当左子树遍历结束时,从栈中弹出一个节点,这个节点是待访问的右子节点(即上一个节点的右子树)node = node.right # 继续访问右子树# 构建链表(右子树按前序遍历顺序连接)size = len(preorderList)for i in range(1, size): # 从第二个节点开始(因为第一个节点已经是链表的头节点)prev, curr = preorderList[i - 1], preorderList[i]prev.left = None # 清空左子树prev.right = curr # 将前一个节点的右指针指向当前节点
时间复杂度:O(n),其中 n 是二叉树的节点数。前序遍历的时间复杂度是 O(n),前序遍历之后,需要对每个节点更新左右子节点的信息,时间复杂度也是 O(n)。
空间复杂度:O(n),其中 n 是二叉树的节点数。空间复杂度取决于栈(递归调用栈或者迭代中显性使用的栈)和存储前序遍历结果的列表的大小,栈内的元素个数不会超过 n,前序遍历列表中的元素个数是 n
方法三:寻找前驱节点
前序遍历访问各节点的顺序是根节点、左子树、右子树。如果一个节点的左子节点为空,则该节点不需要进行展开操作。。如果一个节点的左子节点不为空,则该节点的左子树中的最后一个节点被访问之后,该节点的右子节点被访问。该节点的左子树中最后一个被访问的节点是左子树中的最右边的节点,也是该节点的前驱节点。因此,问题转化成寻找当前节点的前驱节点。
对于当前节点,如果其左子节点不为空,则在其左子树中找到最右边的节点,作为前驱节点,,将当前节点的右子节点赋给前驱节点的右子节点,然后将当前节点的左子节点赋给当前节点的右子节点,并将当前节点的左子节点设为空。对当前节点处理结束后,继续处理链表中的下一个节点,直到所有节点都处理结束。

# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution(object):def flatten(self, root):""":type root: Optional[TreeNode]:rtype: None Do not return anything, modify root in-place instead."""curr=rootwhile curr:if curr.left:predecessor=nxt=curr.left#用来找到左子树中最右的节点while predecessor.right:#找到左子树中的最右节点predecessor=predecessor.right #向右移动,寻找最右边的节点predecessor.right=curr.right#找到左子树中的最右节点后,将当前节点的右子树连接到左子树的最右节点上curr.left=None #当前节点的左子树被置为curr.right=nxt#将当前节点的右指针指向左子树的根节点curr=curr.right #使curr移动到下一个节点(即当前右子树的第一个节点),继续遍历
时间复杂度:O(n)其中 n 是二叉树的节点数。展开为单链表的过程中,需要对每个节点访问一次,在寻找前驱节点的过程中,每个节点最多被额外访问一次
空间复杂度:O(1)
源自力扣官方题解
相关文章:
python-leetcode 45.二叉树转换为链表
题目: 给定二叉树的根节点root,请将它展开为一个单链表: 展开后的单链表应该使用同样的TreeNode,其中right子指针指向链表中的下一个节点,而左子指针始终为空 展开后的单链表应该与二叉树先序遍历顺序相同 方法一:二叉树的前序…...
uni小程序wx.switchTab有时候跳转错误tab问题,解决办法
在一个子页面里面使用uni.switchTab或者wx.switchTab跳转到tab菜单的时候,先发送了一个请求,然后执行跳转到tab菜单,但是这个时候,出错了........也是非常的奇怪,不加请求就没问题......但是业务逻辑就是要先执行某个请…...
【一起学Rust | 框架篇 | Tauri2.0框架】在Tauri应用中设置Http头(Headers)
文章目录 前言一、配置准备1. 检查版本2. 使用条件3. 支持的请求头(并不是全部支持) 二、使用步骤1. 如何配置header2. 框架集成1. 对于Vite系列、Nuxt、Next.js这种前端框架Vite系列框架Angular系列框架Nuxt系列框架Next.js系列框架 2. 对于Yew和Leptos…...
STM32G473VET6 在 Keil MDK 下手动移植 FreeRTOS 指南
下面将详细介绍如何在 Keil MDK 环境下将 FreeRTOS 手动移植到 STM32G473VET6 微控制器上。内容涵盖工程创建、获取源码、文件组织、移植层适配、测试任务编写以及编译调试等步骤。 1. 工程搭建(Keil 项目创建) 创建基础工程:首先准备一个基…...
波导阵列天线 学习笔记11双极化全金属垂直公共馈电平板波导槽阵列天线
摘要: 本communicaition提出了一种双极化全金属垂直公共馈电平板波导槽阵列天线。最初提出了一种公共馈电的单层槽平板波导来实现双极化阵列。此设计消除了传统背腔公共馈电的复杂腔体边缘的必要性,提供了一种更简单的天线结构。在2x2子阵列种发展了宽十…...
DeepSeek-R1自写CUDA内核跑分屠榜:开启GPU编程自动化新时代
引言 在AI领域,深度学习模型的性能优化一直是研究者们关注的核心。最近,斯坦福和普林斯顿的研究团队发现,DeepSeek-R1生成的自定义CUDA内核不仅超越了OpenAI的o1和Claude 3.5 Sonnet,还在KernelBench框架中取得了总排名第一的好成…...
001 Kafka入门及安装
Kafka入门及安装 文章目录 Kafka入门及安装1.介绍Kafka的基本概念和核心组件 2.安装1.docker快速安装zookeeper安装kafka安装 添加topic删除topickafka-ui安装 2.Docker安装(SASL/PLAIN认证配置-用户名密码) 来源参考的deepseek,如有侵权联系…...
2024 年出现的 11 大数据收集趋势
数据收集趋势的出现是对技术进步、企业需求和市场波动的回应,我们对 2025 年的预测涵盖了所有方面。物联网和人工智能等前沿技术将改变组织收集和处理数据的方式,法规将促使它们更加细致地对待数据,而消费者对增强现实和虚拟现实的兴趣将为数…...
动态内容加载的解决方案:Selenium与Playwright对比故障排查实录
方案进程 2024-09-01 09:00 | 接到亚航航班数据采集需求 2024-09-01 11:30 | 首次尝试使用Selenium遭遇Cloudflare验证 2024-09-01 14:00 | 切换Playwright方案仍触发反爬机制 2024-09-01 16:30 | 引入爬虫代理IPUA轮换策略 2024-09-02 10:00 | 双方案完整实现并通过压力测试故…...
OSPF BIT 类型说明
注:本文为 “OSPF BIT 类型 | LSA 类型 ” 相关文章合辑。 机翻,未校。 15 OSPF BIT Types Explained 15 种 OSPF BIT 类型说明 Rashmi Bhardwaj Distribution of routing information within a single autonomous system in larger networks is per…...
java excel xlsx 增加数据验证
隐藏表下拉框 // 创建隐藏工作表存储下拉框数据String hiddenSheetName "HiddenSheet"System.currentTimeMillis();Sheet hiddenSheet workbook.createSheet(hiddenSheetName);//设置隐藏sheetworkbook.setSheetHidden(workbook.getSheetIndex(hiddenSheetName), …...
React + TypeScript 数据血缘分析实战
React TypeScript 数据血缘分析实战 目录 技术选型与架构设计核心概念解析基础场景实现 场景一:visx库基础血缘图实现场景二:React-Lineage-DAG企业级方案场景三:动态数据源与复杂交互 TypeScript类型系统深度优化性能优化与工程化实践开源…...
魔搭 ModelScope 模型下载
wget https://developer.download.nvidia.com/compute/cuda/12.6.0/local_installers/cuda_12.6.0_560.28.03_linux.run sudo sh cuda_12.6.0_560.28.03_linux.run# pip -V pip 24.3.1 # pip3 -V pip 24.3.1设置pip镜像源 # pip config set global.index-url https://mirrors.…...
WorldQuant Brain的专属语言——Fast Expression
使用brain需要的编程语言 在使用BRAIN平台时往往不需要事先有编码背景,因此小白也能很快对其上手,但有经验的程序员来讲,该平台暂时没有禁止API通信低强度进行时的程序化访问(但是非常不好意思😣怎么访问我没找到&…...
在低功耗MCU上实现人工智能和机器学习
作者:Silicon Labs 人工智能(AI)和机器学习(ML)技术不仅正在快速发展,还逐渐被创新性地应用于低功耗的微控制器(MCU)中,从而实现边缘AI/ML解决方案。这些MCU是许多嵌入式…...
MSSQL2022的一个错误:未在本地计算机上注册“Microsoft.ACE.OLEDB.16.0”提供程序
MSSQL2022导入Excel的一个错误:未在本地计算机上注册“Microsoft.ACE.OLEDB.16.0”提供程序 一、导入情况二、问题发现三、问题解决 最近在安装新版SQLServer SSMS 2022后,每次导入Excel都会出现错误提示:未在本地计算机上注册“Microsoft.…...
(2.26 “详细分析示例“ 暴力+位运算 最长优雅子数组)leetcode 2401
a&b0说明a和b的每一位都是一个0和一个1 不存在两个均为1的位次 a|0a 0与任何数|都等于它本身 (mask)的作用: 担心两数的1在用一位导致mask覆盖了? 答:出现这种情况说明mask与nums j后就直接break 由:…...
【洛谷贪心算法题】P1094纪念品分组
该题运用贪心算法,核心思想是在每次分组时,尽可能让价格较小和较大的纪念品组合在一起,以达到最少分组的目的。 【算法思路】 输入处理:首先读取纪念品的数量n和价格上限w,然后依次读取每件纪念品的价格,…...
基于coze+微信小程序的ai对话
界面介绍: 代码:(替换你的coze的配置) <template><view class"container"><!-- 高斯模糊背景 --><view class"animated-bg"><view class"gradient-blob"></view…...
[Linux]项目自动化构建工具-make/Makefile
项目自动化构建工具-make/Makefile make与Makefile单文件Makefile多文件Makefile 缓冲区 首先理清多文件之间的关系: 这里为什么没有包含test.h头文件?因为在当前工作目录下,因此不需要包含test.h,如果把test.h移到上一级目录&…...
工程地质软件市场:发展现状、趋势与策略建议
一、引言 在工程建设领域,准确把握地质条件是确保项目顺利推进和安全运营的关键。工程地质软件作为处理、分析、模拟和展示工程地质数据的重要工具,正发挥着日益重要的作用。它凭借强大的数据处理能力、三维建模功能、空间分析工具和可视化展示手段&…...
华为OD机试-食堂供餐-二分法
import java.util.Arrays; import java.util.Scanner;public class DemoTest3 {public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseint a in.nextIn…...
Swagger和OpenApi的前世今生
Swagger与OpenAPI的关系演进是API标准化进程中的重要篇章,二者共同塑造了现代RESTful API的开发范式。 本期就扒一扒其技术演进的关键节点与核心逻辑: 🔄 一、起源与初创期:Swagger的诞生(2010-2014) 核心…...
用机器学习破解新能源领域的“弃风”难题
音乐发烧友深有体会,玩音乐的本质就是玩电网。火电声音偏暖,水电偏冷,风电偏空旷。至于太阳能发的电,则略显朦胧和单薄。 不知你是否有感觉,近两年家里的音响声音越来越冷,听起来越来越单薄? —…...
【VLNs篇】07:NavRL—在动态环境中学习安全飞行
项目内容论文标题NavRL: 在动态环境中学习安全飞行 (NavRL: Learning Safe Flight in Dynamic Environments)核心问题解决无人机在包含静态和动态障碍物的复杂环境中进行安全、高效自主导航的挑战,克服传统方法和现有强化学习方法的局限性。核心算法基于近端策略优化…...
API网关Kong的鉴权与限流:高并发场景下的核心实践
🔥「炎码工坊」技术弹药已装填! 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 引言 在微服务架构中,API网关承担着流量调度、安全防护和协议转换的核心职责。作为云原生时代的代表性网关,Kong凭借其插件化架构…...
针对药品仓库的效期管理问题,如何利用WMS系统“破局”
案例: 某医药分销企业,主要经营各类药品的批发与零售。由于药品的特殊性,效期管理至关重要,但该企业一直面临效期问题的困扰。在未使用WMS系统之前,其药品入库、存储、出库等环节的效期管理主要依赖人工记录与检查。库…...
WEB3全栈开发——面试专业技能点P4数据库
一、mysql2 原生驱动及其连接机制 概念介绍 mysql2 是 Node.js 环境中广泛使用的 MySQL 客户端库,基于 mysql 库改进而来,具有更好的性能、Promise 支持、流式查询、二进制数据处理能力等。 主要特点: 支持 Promise / async-await…...
webpack面试题
面试题:webpack介绍和简单使用 一、webpack(模块化打包工具)1. webpack是把项目当作一个整体,通过给定的一个主文件,webpack将从这个主文件开始找到你项目当中的所有依赖文件,使用loaders来处理它们&#x…...
Python的__call__ 方法
在 Python 中,__call__ 是一个特殊的魔术方法(magic method),它允许一个类的实例像函数一样被调用。当你在一个对象后面加上 () 并执行时(例如 obj()),Python 会自动调用该对象的 __call__ 方法…...
