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

力扣:105. 从前序与中序遍历序列构造二叉树(Python3)

题目:

给定两个整数数组 preorder 和 inorder ,其中 preorder 是二叉树的先序遍历, inorder 是同一棵树的中序遍历,请构造二叉树并返回其根节点。

来源:力扣(LeetCode)
链接:力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台

示例:

示例 1:

输入:preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出:[3,9,20,null,null,15,7]


示例 2:

输入:preorder = [-1], inorder = [-1]
输出:[-1]

解法:

使用栈辅助(stack),栈中每个结点结构为[当前结点在中序序列中的下标, 树节点],stack初始化的值是前序序列第0个。用栈的目的是当插入结点为右子树时确定其根节点。

遍历前序序列, 从第1个开始。获取当前值在中序序列中的下标,如果比stack中最后1个小,说明当前结点是前个结点的左子树;否则需要弹出栈顶,直到比stack中最后1个大,此时说明当前结点在弹出结点的右边,在栈最后1个结点的左边,所以把当前结点接到弹出结点的右子树。

知识点:

1.前序遍历:根-左-右。

代码:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:root = tree = TreeNode(preorder[0])stack = [[inorder.index(preorder[0]), tree]]for num in preorder[1:]:index = inorder.index(num)tree = TreeNode(num)if index < stack[-1][0]:stack[-1][1].left = treeelse:while stack and index > stack[-1][0]:pre = stack.pop()pre[1].right = treestack.append([index, tree])return root

相关文章:

力扣:105. 从前序与中序遍历序列构造二叉树(Python3)

题目&#xff1a; 给定两个整数数组 preorder 和 inorder &#xff0c;其中 preorder 是二叉树的先序遍历&#xff0c; inorder 是同一棵树的中序遍历&#xff0c;请构造二叉树并返回其根节点。 来源&#xff1a;力扣&#xff08;LeetCode&#xff09; 链接&#xff1a;力扣&am…...

【含java2023面试题】HashMap、HashTable、ConcurrentHashMap

作为Java中最常用的Map集合&#xff0c;HashMap、HashTable和ConcurrentHashMap都是线程安全的&#xff0c;但它们之间有什么区别呢&#xff1f;在本文中&#xff0c;我们将深入探讨这三种Map集合的区别&#xff0c;并通过Java代码示例来演示它们之间的差异。 AI绘画关于SD,MJ…...

AT24C02芯片

AT24C02简介&#xff1a; AT24C01/02/04/08/16...是一个 1K/2K/4K/8K/16K 位串行 CMOS内部有9个字节&#xff1b; 该器件通过 I2C 总线接口进行 操作&#xff0c;它有一个专门的写保护功能&#xff1b; 基于51 他有这个芯片操作 时序&#xff1a; AT24C02软件编程&#xff1a; …...

Python+Django前后端分离

程序示例精选 PythonDjango前后端分离 如需安装运行环境或远程调试&#xff0c;见文章底部个人QQ名片&#xff0c;由专业技术人员远程协助&#xff01; 前言 这篇博客针对《PythonDjango前后端分离》编写代码&#xff0c;代码整洁&#xff0c;规则&#xff0c;易读。 学习与应…...

win11系统固定到快速访问的文件夹无法调整顺序的问题

最近在使用win11系统时&#xff0c;固定到快速访问的文件夹无法调整顺序。网上搜了一大圈没有对应的解决方法&#xff0c;柳暗花明&#xff0c;在博主yin0hao的一篇文章中找到了类似的&#xff0c;跟着做了一下&#xff0c;结果问题也解决了。在此记录。 在文件资源管理器地址…...

短视频矩阵系统,短视频矩阵源码技术开发

开发短视频矩阵系统的源码需要以下步骤&#xff1a; 确定系统需求&#xff1a;根据客户的需求&#xff0c;确定系统的功能和特点&#xff0c;例如用户注册登录、视频上传、视频浏览、评论点赞等。 设计系统架构&#xff1a;根据系统需求&#xff0c;设计系统的整体架构&#x…...

Flask 数据库 连接池、DBUtils、http 连接池

1、DBUtils 简介、使用 DBUtils 简介 DBUtils 是一套用于管理 数据库 "连接池" 的Python包&#xff0c;为 "高频度、高并发" 的数据库访问提供更好的性能&#xff0c;可以自动管理连接对象的创建和释放。并允许对非线程安全的数据库接口进行线程安全包装…...

Day 01 python学习笔记

1、引入 让我们先写第一个python程序&#xff08;如果是纯小白的话&#xff09; 因为我们之前安装了python解释器 所以我们直接win r ---->输入cmd&#xff08;打开运行终端&#xff09; >python #&#xff08;在终端中打开python解释器&#xff09;>>>pri…...

CSharp Library develop histroy

1. .NET FRAMEWORK 发展版本 版本 完整版本号 发行日期 Visual Studio Windows 默认安装 1.0 1.0.3705.0 2002-02-13 Visual Studio .NET 2002 Windows XP Media Center Edition Windows XP Tablet PC Edition 1.1 1.1.4322.573 2003-04-24 Visual Studio .NET 2…...

林木种苗生产vr虚拟实训教学降低培训等待周期

林业种植管理在保护水土流失、气候变化及经济社会发展中发挥重要的作用&#xff0c;林业教学往往需要进入林区进行实操察验&#xff0c;在安全性、时间及效率上难以把控&#xff0c;因此有更多林业畜牧院校创新性地引进VR虚拟现实技术。 在林业领域&#xff0c;实地调查是获取准…...

LabVIEW在运行时调整表控件列宽

LabVIEW在运行时调整表控件列宽 如何在LabIEW中运行时调整表控件的列宽大小&#xff1f; 在VI运行时&#xff0c;有两种不同的方法可以更改表中列的宽度。首先&#xff0c;可以使用鼠标手动更改它们;其次&#xff0c;可以从框图中以编程方式更改它们。 手动更改列宽 只有在…...

【6 ElementUI Tabs控件第二个tab页签Div宽度缩小的问题】

背景 在使用ElementUI的Tabs 控件时&#xff0c;发现第二个tabs 内容的Div宽度用的百分比&#xff0c;然后就会缩小&#xff0c;导致内容变形&#xff0c;这边的处理方法就是拿到一个tabs 内容的div的offsetWidth&#xff0c;然后将这个width赋值给第二个Div的width即可。 代…...

读写分离MySQL

利用Mycat控制后台数据库的读写分离和负载均衡 利用主从复制思想,实现读写分离,主库写,从库读 从库最好不要写,因为从库写入的数据不能同步到主库,只有主库写的数据才能同步到从库 balance属性值对应的含义(负载均衡) 一主一从读写分离的弊端 主节点Master宕机以后,业务系统…...

MySQL数据库用户管理

MySQL数据库用户管理 1、数据库权限1.1什么是数据库权限1.2数据库权限分类1.3用户管理 2、用户授权2.1grant提权2.2查看权限2.3撤销权限 3、修改密码3.1修改当前用户密码3.2修改其他用户密码3.3修改root密码 4、远程登录4.1远程登录4.2软件远程登录 5、总结 1、数据库权限 1.1…...

package.json属性

添加链接描述 一、必须属性 name 定义项目的名称&#xff0c;不能以".“和”_"开头&#xff0c;不能包含大写字母version 定义项目的版本号&#xff0c;格式为&#xff1a;大版本号.次版本号.修订号 二、描述信息 description 项目描述keywords 项目关键词author …...

C# 把m4a格式文件转为MP3格式

直接上代码&#xff1a; 先引用 using NAudio.Wave; using NAudio.Lame; 1, 文件列表来自于根目录里所有的m4a文件 string directloc "G:\mp3\MP3"; string[] fyles Directory.GetFiles(directloc); NAudio.Wave.BlockAlignReductionStream stream …...

【分享】Word文档如何批量转换成PDF?

Word格式比较容易编辑&#xff0c;是工作中经常用到的文档工具&#xff0c;有时候为了避免文档在传送中出现乱码&#xff0c;或者防止被随意更改&#xff0c;很多人会把Word文档转换成PDF&#xff0c;那Word文档要怎样转成PDF呢&#xff1f;如果Word文档很多&#xff0c;有没有…...

dedecms tag 伪静态 数字版本

织梦伪静态将tag标签的url设置成id的方法&#xff1a; 1、在网站根目录下的tags.php中18行找到&#xff1a; if(isset($tags[2])) $PageNo intval($tags[2]);在其下方加入代码&#xff1a; $tagid intval($tag); if(!empty($tagid)) {$row $dsql->GetOne("SELECT …...

mysql数据库ip被阻断

windos服务器还是 linux服务器没关系。 登录服务器mysql 授权法。 例如&#xff0c;你想myuser使用mypassword从任何主机连接到mysql服务器的话。 GRANT ALL PRIVILEGES ON *.* TO myuser% IDENTIFIED BY mypassword WITH GRANT OPTION如果你想允许用户myuser…...

Nginx WEB访问与Linux授权约束

看到所有文件的权限都是没有的&#xff0c;即便所有的权限都没有即使nginx做了配置&#xff0c;这些都是正确的。那么在浏览器真正去访问的时候是不能访问的。 [rootjenkins html]# ls -l total 4 drwxr-xr-x 2 root root 23 Sep 16 17:43 dist ---------- 1 root root 33 Sep …...

简易版抽奖活动的设计技术方案

1.前言 本技术方案旨在设计一套完整且可靠的抽奖活动逻辑,确保抽奖活动能够公平、公正、公开地进行,同时满足高并发访问、数据安全存储与高效处理等需求,为用户提供流畅的抽奖体验,助力业务顺利开展。本方案将涵盖抽奖活动的整体架构设计、核心流程逻辑、关键功能实现以及…...

dedecms 织梦自定义表单留言增加ajax验证码功能

增加ajax功能模块&#xff0c;用户不点击提交按钮&#xff0c;只要输入框失去焦点&#xff0c;就会提前提示验证码是否正确。 一&#xff0c;模板上增加验证码 <input name"vdcode"id"vdcode" placeholder"请输入验证码" type"text&quo…...

自然语言处理——Transformer

自然语言处理——Transformer 自注意力机制多头注意力机制Transformer 虽然循环神经网络可以对具有序列特性的数据非常有效&#xff0c;它能挖掘数据中的时序信息以及语义信息&#xff0c;但是它有一个很大的缺陷——很难并行化。 我们可以考虑用CNN来替代RNN&#xff0c;但是…...

算法岗面试经验分享-大模型篇

文章目录 A 基础语言模型A.1 TransformerA.2 Bert B 大语言模型结构B.1 GPTB.2 LLamaB.3 ChatGLMB.4 Qwen C 大语言模型微调C.1 Fine-tuningC.2 Adapter-tuningC.3 Prefix-tuningC.4 P-tuningC.5 LoRA A 基础语言模型 A.1 Transformer &#xff08;1&#xff09;资源 论文&a…...

《C++ 模板》

目录 函数模板 类模板 非类型模板参数 模板特化 函数模板特化 类模板的特化 模板&#xff0c;就像一个模具&#xff0c;里面可以将不同类型的材料做成一个形状&#xff0c;其分为函数模板和类模板。 函数模板 函数模板可以简化函数重载的代码。格式&#xff1a;templa…...

20个超级好用的 CSS 动画库

分享 20 个最佳 CSS 动画库。 它们中的大多数将生成纯 CSS 代码&#xff0c;而不需要任何外部库。 1.Animate.css 一个开箱即用型的跨浏览器动画库&#xff0c;可供你在项目中使用。 2.Magic Animations CSS3 一组简单的动画&#xff0c;可以包含在你的网页或应用项目中。 3.An…...

STM32HAL库USART源代码解析及应用

STM32HAL库USART源代码解析 前言STM32CubeIDE配置串口USART和UART的选择使用模式参数设置GPIO配置DMA配置中断配置硬件流控制使能生成代码解析和使用方法串口初始化__UART_HandleTypeDef结构体浅析HAL库代码实际使用方法使用轮询方式发送使用轮询方式接收使用中断方式发送使用中…...

tomcat入门

1 tomcat 是什么 apache开发的web服务器可以为java web程序提供运行环境tomcat是一款高效&#xff0c;稳定&#xff0c;易于使用的web服务器tomcathttp服务器Servlet服务器 2 tomcat 目录介绍 -bin #存放tomcat的脚本 -conf #存放tomcat的配置文件 ---catalina.policy #to…...

从面试角度回答Android中ContentProvider启动原理

Android中ContentProvider原理的面试角度解析&#xff0c;分为​​已启动​​和​​未启动​​两种场景&#xff1a; 一、ContentProvider已启动的情况 1. ​​核心流程​​ ​​触发条件​​&#xff1a;当其他组件&#xff08;如Activity、Service&#xff09;通过ContentR…...

如何配置一个sql server使得其它用户可以通过excel odbc获取数据

要让其他用户通过 Excel 使用 ODBC 连接到 SQL Server 获取数据&#xff0c;你需要完成以下配置步骤&#xff1a; ✅ 一、在 SQL Server 端配置&#xff08;服务器设置&#xff09; 1. 启用 TCP/IP 协议 打开 “SQL Server 配置管理器”。导航到&#xff1a;SQL Server 网络配…...