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

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对话

界面介绍&#xff1a; 代码&#xff1a;&#xff08;替换你的coze的配置&#xff09; <template><view class"container"><!-- 高斯模糊背景 --><view class"animated-bg"><view class"gradient-blob"></view…...

[Linux]项目自动化构建工具-make/Makefile

项目自动化构建工具-make/Makefile make与Makefile单文件Makefile多文件Makefile 缓冲区 首先理清多文件之间的关系&#xff1a; 这里为什么没有包含test.h头文件&#xff1f;因为在当前工作目录下&#xff0c;因此不需要包含test.h&#xff0c;如果把test.h移到上一级目录&…...

19c补丁后oracle属主变化,导致不能识别磁盘组

补丁后服务器重启&#xff0c;数据库再次无法启动 ORA01017: invalid username/password; logon denied Oracle 19c 在打上 19.23 或以上补丁版本后&#xff0c;存在与用户组权限相关的问题。具体表现为&#xff0c;Oracle 实例的运行用户&#xff08;oracle&#xff09;和集…...

DeepSeek 赋能智慧能源:微电网优化调度的智能革新路径

目录 一、智慧能源微电网优化调度概述1.1 智慧能源微电网概念1.2 优化调度的重要性1.3 目前面临的挑战 二、DeepSeek 技术探秘2.1 DeepSeek 技术原理2.2 DeepSeek 独特优势2.3 DeepSeek 在 AI 领域地位 三、DeepSeek 在微电网优化调度中的应用剖析3.1 数据处理与分析3.2 预测与…...

VB.net复制Ntag213卡写入UID

本示例使用的发卡器&#xff1a;https://item.taobao.com/item.htm?ftt&id615391857885 一、读取旧Ntag卡的UID和数据 Private Sub Button15_Click(sender As Object, e As EventArgs) Handles Button15.Click轻松读卡技术支持:网站:Dim i, j As IntegerDim cardidhex, …...

在 Nginx Stream 层“改写”MQTT ngx_stream_mqtt_filter_module

1、为什么要修改 CONNECT 报文&#xff1f; 多租户隔离&#xff1a;自动为接入设备追加租户前缀&#xff0c;后端按 ClientID 拆分队列。零代码鉴权&#xff1a;将入站用户名替换为 OAuth Access-Token&#xff0c;后端 Broker 统一校验。灰度发布&#xff1a;根据 IP/地理位写…...

第 86 场周赛:矩阵中的幻方、钥匙和房间、将数组拆分成斐波那契序列、猜猜这个单词

Q1、[中等] 矩阵中的幻方 1、题目描述 3 x 3 的幻方是一个填充有 从 1 到 9 的不同数字的 3 x 3 矩阵&#xff0c;其中每行&#xff0c;每列以及两条对角线上的各数之和都相等。 给定一个由整数组成的row x col 的 grid&#xff0c;其中有多少个 3 3 的 “幻方” 子矩阵&am…...

scikit-learn机器学习

# 同时添加如下代码, 这样每次环境(kernel)启动的时候只要运行下方代码即可: # Also add the following code, # so that every time the environment (kernel) starts, # just run the following code: import sys sys.path.append(/home/aistudio/external-libraries)机…...

MyBatis中关于缓存的理解

MyBatis缓存 MyBatis系统当中默认定义两级缓存&#xff1a;一级缓存、二级缓存 默认情况下&#xff0c;只有一级缓存开启&#xff08;sqlSession级别的缓存&#xff09;二级缓存需要手动开启配置&#xff0c;需要局域namespace级别的缓存 一级缓存&#xff08;本地缓存&#…...

Ubuntu系统复制(U盘-电脑硬盘)

所需环境 电脑自带硬盘&#xff1a;1块 (1T) U盘1&#xff1a;Ubuntu系统引导盘&#xff08;用于“U盘2”复制到“电脑自带硬盘”&#xff09; U盘2&#xff1a;Ubuntu系统盘&#xff08;1T&#xff0c;用于被复制&#xff09; &#xff01;&#xff01;&#xff01;建议“电脑…...

鸿蒙(HarmonyOS5)实现跳一跳小游戏

下面我将介绍如何使用鸿蒙的ArkUI框架&#xff0c;实现一个简单的跳一跳小游戏。 1. 项目结构 src/main/ets/ ├── MainAbility │ ├── pages │ │ ├── Index.ets // 主页面 │ │ └── GamePage.ets // 游戏页面 │ └── model │ …...

jdbc查询mysql数据库时,出现id顺序错误的情况

我在repository中的查询语句如下所示&#xff0c;即传入一个List<intager>的数据&#xff0c;返回这些id的问题列表。但是由于数据库查询时ID列表的顺序与预期不一致&#xff0c;会导致返回的id是从小到大排列的&#xff0c;但我不希望这样。 Query("SELECT NEW com…...