当前位置: 首页 > 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 …...

YSYX学习记录(八)

C语言&#xff0c;练习0&#xff1a; 先创建一个文件夹&#xff0c;我用的是物理机&#xff1a; 安装build-essential 练习1&#xff1a; 我注释掉了 #include <stdio.h> 出现下面错误 在你的文本编辑器中打开ex1文件&#xff0c;随机修改或删除一部分&#xff0c;之后…...

基于Docker Compose部署Java微服务项目

一. 创建根项目 根项目&#xff08;父项目&#xff09;主要用于依赖管理 一些需要注意的点&#xff1a; 打包方式需要为 pom<modules>里需要注册子模块不要引入maven的打包插件&#xff0c;否则打包时会出问题 <?xml version"1.0" encoding"UTF-8…...

【学习笔记】深入理解Java虚拟机学习笔记——第4章 虚拟机性能监控,故障处理工具

第2章 虚拟机性能监控&#xff0c;故障处理工具 4.1 概述 略 4.2 基础故障处理工具 4.2.1 jps:虚拟机进程状况工具 命令&#xff1a;jps [options] [hostid] 功能&#xff1a;本地虚拟机进程显示进程ID&#xff08;与ps相同&#xff09;&#xff0c;可同时显示主类&#x…...

ArcGIS Pro制作水平横向图例+多级标注

今天介绍下载ArcGIS Pro中如何设置水平横向图例。 之前我们介绍了ArcGIS的横向图例制作&#xff1a;ArcGIS横向、多列图例、顺序重排、符号居中、批量更改图例符号等等&#xff08;ArcGIS出图图例8大技巧&#xff09;&#xff0c;那这次我们看看ArcGIS Pro如何更加快捷的操作。…...

Spring AI与Spring Modulith核心技术解析

Spring AI核心架构解析 Spring AI&#xff08;https://spring.io/projects/spring-ai&#xff09;作为Spring生态中的AI集成框架&#xff0c;其核心设计理念是通过模块化架构降低AI应用的开发复杂度。与Python生态中的LangChain/LlamaIndex等工具类似&#xff0c;但特别为多语…...

基于Java+MySQL实现(GUI)客户管理系统

客户资料管理系统的设计与实现 第一章 需求分析 1.1 需求总体介绍 本项目为了方便维护客户信息为了方便维护客户信息&#xff0c;对客户进行统一管理&#xff0c;可以把所有客户信息录入系统&#xff0c;进行维护和统计功能。可通过文件的方式保存相关录入数据&#xff0c;对…...

推荐 github 项目:GeminiImageApp(图片生成方向,可以做一定的素材)

推荐 github 项目:GeminiImageApp(图片生成方向&#xff0c;可以做一定的素材) 这个项目能干嘛? 使用 gemini 2.0 的 api 和 google 其他的 api 来做衍生处理 简化和优化了文生图和图生图的行为(我的最主要) 并且有一些目标检测和切割(我用不到) 视频和 imagefx 因为没 a…...

GruntJS-前端自动化任务运行器从入门到实战

Grunt 完全指南&#xff1a;从入门到实战 一、Grunt 是什么&#xff1f; Grunt是一个基于 Node.js 的前端自动化任务运行器&#xff0c;主要用于自动化执行项目开发中重复性高的任务&#xff0c;例如文件压缩、代码编译、语法检查、单元测试、文件合并等。通过配置简洁的任务…...

【前端异常】JavaScript错误处理:分析 Uncaught (in promise) error

在前端开发中&#xff0c;JavaScript 异常是不可避免的。随着现代前端应用越来越多地使用异步操作&#xff08;如 Promise、async/await 等&#xff09;&#xff0c;开发者常常会遇到 Uncaught (in promise) error 错误。这个错误是由于未正确处理 Promise 的拒绝&#xff08;r…...

Axure 下拉框联动

实现选省、选完省之后选对应省份下的市区...