力扣: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

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/140496.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Visio——绘制倾斜线段

一、形状 -> 图表和数学图形 -> 多行 二、放置多行线&#xff0c;可以发现存在两个折点 三、选择多行线&#xff0c;右键选择删除点&#xff0c;即可得到倾斜线段

C进阶-数据的存储

数据类型介绍 内置类型&#xff1a; //数据类型中的内置类型 // char //字符数据类型 // short //短整型 // int //整型 // long //长整型 // long long //更长的整型 // float //单精度浮点数 // double //双精度浮点数 //数据类型中的内置类型 单位是字节 // char //字…

PyCharm 手动下载插件

插件模块一直加载失败&#xff0c;报错信息&#xff1a; Marketplace plugins are not loaded. Check the internet connection and refresh. 尝试了以下方法&#xff0c;均告失败&#xff1a; pip 换源Manage Plugin Repositories...HTTP 代理设置...关闭三个防火墙 最后选…

《动手学深度学习 Pytorch版》 7.4 含并行连接的网络(GoogLeNet)

import torch from torch import nn from torch.nn import functional as F from d2l import torch as d2l7.4.1 Inception块 GoogLNet 中的基本卷积块叫做 Inception 块&#xff08;大概率得名于盗梦空间&#xff09;&#xff0c;由 4 条并行路径组成。 前 3 条路径使用窗口…

华为云云耀云服务器L实例评测|使用云耀云服务器L实例,自行搭建NextCloud

背景 本人是搞分布式存储的&#xff0c;一心想搭个网盘&#xff0c;发现L实例里面就有个网盘实例最低配置是2核4G&#xff0c;为了节省成本&#xff0c;选个【2核2G】的配置&#xff0c;一样可以搭起来。 简介 Nextcloud是一款开源免费的私有云存储网盘项目&#xff0c;可以让…

clickhouse学习之路----clickhouse的特点及安装

clickhouse学习笔记 反正都有学不完的技术&#xff0c;不如就学一学clickhouse吧 文章目录 clickhouse学习笔记clickhouse的特点1.列式存储2. DBMS 的功能3.多样化引擎4.高吞吐写入能力5.数据分区与线程级并行 clickhouse安装1.关闭防火墙2.CentOS 取消打开文件数限制3.安装依…

DATE和LocalDateTime在Java中有什么区别

在Java中&#xff0c;Date和LocalDateTime是两个表示日期和时间的类&#xff0c;它们有以下区别&#xff1a; 类型&#xff1a;Date是Java旧版提供的日期和时间类&#xff0c;而LocalDateTime是Java 8引入的新日期和时间API中的类。 不可变性&#xff1a;Date是可变类&#x…

深入理解C#中委托的使用及不同类型委托的应用示例

在C#中&#xff0c;委托是一种强大而灵活的机制&#xff0c;可以引用一个或多个方法&#xff0c;并允许以类似函数指针的方式进行调用。委托在事件处理、回调函数和多线程编程等场景中非常有用。本文将深入探讨C#中委托的使用&#xff0c;并介绍不同类型委托的应用示例。 目录…

Fiddler抓包工具配置+Jmeter基本使用

一、Fiddler抓包工具的配置和使用 在编写网关自动化脚本之前&#xff0c;得先学会如何抓包&#xff0c;这里以Fiddler为例。会抓包的同学可以跳过这一步&#xff0c;当然看看也是没坏处的…… 局域网络配置 将要进行抓包的手机与电脑连入同一局域网&#xff0c;电脑才能够抓到…

【深度学习实验】前馈神经网络(八):模型评价(自定义支持分批进行评价的Accuracy类)

目录 一、实验介绍 二、实验环境 1. 配置虚拟环境 2. 库版本介绍 三、实验内容 0. 导入必要的工具包 1. __init__(构造函数) 2. update函数(更新评价指标) 5. accumulate(计算准确率) 4. reset(重置评价指标) 5. 构造数据进行测试 6. 代码整合 一、实验介绍 本文将实…

react多条件查询

1、声明一个filter常量 2.filter接受&#xff08;condition,data&#xff09;两个参数 3、调用data里面的filter进行筛选 4、任意一个item当筛选条件 5、使用object.key获取对象所有key 6、对每个key使用Array.prototype.every&#xff08;&#xff09;方法判断是否满足条…

华为数通方向HCIP-DataCom H12-821题库(单选题:361-380)

第361题 如图所示是一台路由器的BGP输出信息。那么以下关于这段信息的描述,错误的是哪一项? <Huawei>display bgp error Error Type: Peer Error Peer Address:10.1.1.2 VRFName:Public Error Info: Router-ID conflictA、该路由器邻居地址是10.1.1.2 B、Error Type显…

电脑计算机xinput1_3.dll丢失的解决方法分享,四种修复手段解决问题

日常生活中可能会遇到的问题——xinput1_3.dll丢失的解决方法。我相信&#xff0c;在座的很多朋友都曾遇到过这个问题&#xff0c;那么接下来&#xff0c;我将分享如何解决这个问题的解决方法。 首先&#xff0c;让我们来了解一下xinput1_3.dll文件。xinput1_3.dll是一个动态链…

【数据结构】什么是数据结构?

数据结构(Data Structure)是计算机存储,组织数据的方式,指相互之间存在一种或多种特定关系的数据元素的集合. 这么讲可能有些抽象,放一张图大家可能好理解一点: 上图依次是数据结构中逻辑结构中的:集合结构,线性结构,树形结构,图形结构. 而: 数据结构是一门研究非数值计算的程…

分库分表MySQL

目录 Mycat入门 分片配置 分片配置(配置Mycat的用户以及用户的权限) 启动服务 登录Mycat Mycat配置 schema.xml 1.schema标签:配置逻辑库,逻辑表的相关信息 1-1.核心属性 1-2.table标签 2.datanode标签:配置数据节点的相关信息 核心属性 3.datahost标签:配置的是节…

【性能测试】JMeter:集合点,同步定时器的应用实例!

一、集合点的定义 在性能测试过程中&#xff0c;为了真实模拟多个用户同时进行操作以度量服务器的处理能力&#xff0c;可以考虑同步虚拟用户以便恰好在同一时刻执行操作或发送请求。 通过插入集合点可以较真实模拟多个用户并发操作。 (注意&#xff1a;虽然通过加入集合点可…

蓝牙核心规范(V5.4)10.2-BLE 入门笔记之CIS篇

LE CIS 同步通信 同步通信提供了一种使用蓝牙LE在设备之间传输有时间限制的数据的方式。它提供了一个机制,允许多个接收器设备在不同的时间从相同的源接收数据,以同步它们对该数据的处理。LE AUDIO使用同步通信。 当使用同步通信时,数据具有有限的时间有效期,在到期时被认…

第1篇 目标检测概述 —(1)目标检测基础知识

前言&#xff1a;Hello大家好&#xff0c;我是小哥谈。目标检测是计算机视觉领域中的一项任务&#xff0c;旨在自动识别和定位图像或视频中的特定目标&#xff0c;目标可以是人、车辆、动物、物体等。目标检测的目标是从输入图像中确定目标的位置&#xff0c;并使用边界框将其标…

Linux指令(ls、pwd、cd、touch、mkdir、rm)

whoami who pwd ls ls -l clearls指令 ls ls -l ls -a :显示当前目录下的隐藏文件&#xff08;隐藏文件以.开头&#xff09;ls -a -l 和 ls -l -a 和 ls -la 和 ls -al &#xff08;等价于ll&#xff09; pwd命令 显示用户当前所在的目录 cd指令 mkdir code &#xff08;创建…

PPT系统化学习 - 第1天

文章目录 更改PPT主题更改最大撤回次数自动保存禁止PPT压缩图片字体嵌入PPTPPT导出为PDFPPT导出为图片PPT导出为图片型幻灯片PPT导出成视频添加参考线设置默认字体设置默认形状建立模板、保存模板、使用模板建立模板保存模板使用模板 更改PPT主题 更改PPT的主题&#xff1a; 夜…