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

【算法】leetcode 105 从前序与中序遍历序列构造二叉树

题目

输入某二叉树的前序遍历和中序遍历的结果,请构建该二叉树并返回其根节点。

假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

示例 1:

Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]

示例 2:

Input: preorder = [-1], inorder = [-1]
Output: [-1]

限制:

0 <= 节点个数 <= 5000

解答

#include <iostream>
#include <unordered_map>
#include <vector>using namespace std;struct TreeNode
{int val;TreeNode *left;TreeNode *right;TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};class Solution {
public:TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {for (int i = 0; i < inorder.size(); i++){// 用中序遍历数组建立 值-下标 的映射value_index[inorder[i]] = i;}return recursive(preorder,0, 0, inorder.size() - 1);}TreeNode *recursive(vector<int>& pre,int pre_root, int in_left, int in_right){if (in_left > in_right) return nullptr;// 将对应的 val 赋给 node 节点TreeNode *node = new TreeNode(pre[pre_root]);int in_root = value_index[pre[pre_root]];node->left = recursive(pre,pre_root + 1, in_left, in_root - 1);node->right = recursive(pre,pre_root + in_root - in_left + 1, in_root + 1, in_right);return node;}
private:unordered_map<int, int> value_index;
};

相关文章:

【算法】leetcode 105 从前序与中序遍历序列构造二叉树

题目 输入某二叉树的前序遍历和中序遍历的结果&#xff0c;请构建该二叉树并返回其根节点。 假设输入的前序遍历和中序遍历的结果中都不含重复的数字。 示例 1: Input: preorder [3,9,20,15,7], inorder [9,3,15,20,7] Output: [3,9,20,null,null,15,7]示例 2: Input: pr…...

11 | Spark计算数据文件中每行数值的平均值

需求:计算数据文件中的数值的平均值 背景: 你有一个数据文件,其中包含一系列数值,每行一个数值,数值之间用逗号分隔。你想使用Apache Spark分布式计算框架来读取数据文件中的数值并计算它们的平均值。功能要求: 通过Spark配置和上下文初始化Spark应用程序。从数据文件中…...

AI与游戏创新:深度学习的起跑枪声

《AI与游戏创新&#xff1a;深度学习的起跑枪声》 目录 引言AIGC定义与重要性AI在游戏中的应用AI推动游戏创新的可能途径AIGC的挑战与解决方案结论&#xff1a;AI是游戏行业的下一站 引言 AI&#xff08;人工智能&#xff09;正在全球范围内改变各个行业&#xff0c;游戏行…...

【GUI开发】用python爬YouTube博主信息,并开发成exe软件

文章目录 一、背景介绍二、代码讲解2.1 爬虫2.2 tkinter界面2.3 存日志 三、软件演示视频四、说明 一、背景介绍 你好&#xff0c;我是马哥python说&#xff0c;一名10年程序猿。 最近我用python开发了一个GUI桌面软件&#xff0c;目的是爬取相关YouTube博主的各种信息&#…...

7.6 函数的递归调用

直接调用&#xff1a; ### 1. 直接递归调用 直接递归调用是指一个函数直接调用自己。例如&#xff0c;计算阶乘的函数&#xff0c;可以使用递归方法&#xff1a; int factorial(int n) {if (n < 1) {return 1;}return n * factorial(n - 1); } 在这个例子中&#xff0c;f…...

本地开机启动jar

1&#xff1a;首先有个可运行的jar包 本地以ruiyi代码为例打包 2&#xff1a;编写bat命令---命名为.bat即可 echo off java -jar D:\everyDay\test\RuoYi\target\RuoYi.jar 3&#xff1a;设置为开机自启动启动 快捷键winr----输入shell:startup---打开启动文档夹 把bat文件复…...

解决uniapp手机真机调试时找不到手机问题

1、检查 USB 调试是否开启 2、检查是否有选择 文件 传输 选项 3、如果上述都做了还找不到&#xff0c;可以看看开发者选项中的【USB设置】&#xff0c;把模式改为 MIDI 模式...

HarmonyOS应用开发者-----高级认证试题及答案

HarmonyOS应用开发者高级认证试题及答案 试题会不定时刷新,本试题仅供大家学习参考 【判断题】 2/2 HarmonyOS应用可以兼容OpenHarmony生态 正确(True)【判断题】 2/2 所有使用@Component修饰的自定义组件都支持onPageShow,onBackPress和onPageHide生命周期函数。 正确(True…...

R语言随机波动模型SV:马尔可夫蒙特卡罗法MCMC、正则化广义矩估计和准最大似然估计上证指数收益时间序列...

全文链接&#xff1a;http://tecdat.cn/?p31162 最近我们被客户要求撰写关于SV模型的研究报告&#xff0c;包括一些图形和统计输出&#xff08;点击文末“阅读原文”获取完整代码数据&#xff09;。 相关视频 本文做SV模型&#xff0c;选取马尔可夫蒙特卡罗法(MCMC)、正则化广…...

详细教程:Stegsolve的下载,jdk的下载、安装以及环境的配置

最近在学习隐写术&#xff0c;下载stegsolve 以及使用stegsolve倒腾了很久&#xff0c;避免朋友们和我一样倒腾了很久&#xff0c;希望此文可以帮到刚在学习隐写的朋友们(win7下使用stegsolve) 文章目录 一、下载stegsolve链接二、jdk的下载三、jdk的安装四、配置环境变量五、检…...

Watermark 是怎么生成和传递的?

分析&回答 Watermark 介绍 Watermark 本质是时间戳&#xff0c;与业务数据一样无差别地传递下去&#xff0c;目的是衡量事件时间的进度&#xff08;通知 Flink 触发事件时间相关的操作&#xff0c;例如窗口&#xff09;。 Watermark 是一个时间戳, 它表示小于该时间戳的…...

深度学习论文分享(八)Learning Event-Driven Video Deblurring and Interpolation

深度学习论文分享&#xff08;八&#xff09;Learning Event-Driven Video Deblurring and Interpolation 前言Abstract1 Introduction2 Motivation2.1 Physical Model of Event-based Video Reconstruction2.2 Spatially Variant Triggering Threshold 3 Proposed Methods3.1 …...

UI设计开发原则

一、一致性原则 坚持以用户体验为中心设计原则&#xff0c;界面直观、简洁&#xff0c;操作方便快捷&#xff0c;用户接触软件后对界面上对应的功能一目了然、不需要太多培训就可以方便使用本应用系统。 1、字体 保持字体及颜色一致&#xff0c;避免一套主题出现多个字体&am…...

Mac 如何判断下载Mac with Intel Chip 还是 Mac with Apple Chip

如下图&#xff0c;当我们在 Mac系统 下载客户端时&#xff0c;有两种选择&#xff1a;Mac with Intel Chip 、 Mac with Apple Chip 如何判断要下载哪一种&#xff1f; 需要判断本机Mac是在Inter芯片还是Apple芯片上运行的。方法如下&#xff1a; 点击屏幕左上角Apple标志&a…...

windows笔记本远程连接如何打开任务管理器?

参考素材&#xff1a; https://jingyan.baidu.com/article/8275fc86a97f5207a03cf6cd.html https://www.anyviewer.cn/how-to/ctrl-alt-delete-remote-desktop-6540.html 网上查了很多方法&#xff0c;都说ctrlaltend可以解决这个问题。 但是笔记本键盘上没有end键。 继续查了一…...

GitHub打不开解决方法——授人以渔

打不开GitHub的原因之一&#xff0c;DNS地址解析到了无法访问的ip。&#xff08;为什么无法访问&#xff1f;&#xff09; 1、打开GitHub看是哪个域名无法访问&#xff0c;F12一下 2、DNS解析看对应的域名目前哪个IP可以访问 DNS解析的网址&#xff1a; &#xff08;1&#x…...

gRPC之数据压缩Snappy、zstd

文章目录 gRPC之数据压缩Snappy一、背景二、什么是snappy1. Snappy适合场景 三、demo: Go代码实现了一个snappy压缩格式的压缩器for grpc1. 这段代码怎么保证并发安全的&#xff1f; 四、什么是zstd五、 zstd和snappy有什么区别,如何选择?六、demo: Go代码实现了一个zstd压缩格…...

k8s之存储篇---存储类StorageClass

介绍 StorageClass 为管理员提供了描述存储"类"的方法。 不同的类型可能会映射到不同的服务质量等级或备份策略&#xff0c;或是由集群管理员制定的任意策略。 Kubernetes 本身并不清楚各种类代表的什么。这个类的概念在其他存储系统中有时被称为"配置文件&quo…...

WordPress(4)关于网站的背景图片更换

提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 文章目录 前言一、更改的位置1. 红色区域是要更换的随机的图片二、替换图片位置三.开启随机数量四.结束前言 提示:这里可以添加本文要记录的大概内容: 例如:随着人工智能的不断发展,机器学习这门技术也…...

2 | Window 搭建单机 Hadoop 和Spark

搭建单机 Hadoop 和 Spark 环境可以学习和测试大数据处理的基础知识。在 Windows 操作系统上搭建这两个工具需要一些配置和设置,下面是一个详细的教程: 注意: 在开始之前,请确保你已经安装了 Java 开发工具包(JDK),并且已经下载了 Hadoop 和 Spark 的最新版本。你可以从…...

零门槛NAS搭建:WinNAS如何让普通电脑秒变私有云?

一、核心优势&#xff1a;专为Windows用户设计的极简NAS WinNAS由深圳耘想存储科技开发&#xff0c;是一款收费低廉但功能全面的Windows NAS工具&#xff0c;主打“无学习成本部署” 。与其他NAS软件相比&#xff0c;其优势在于&#xff1a; 无需硬件改造&#xff1a;将任意W…...

iOS 26 携众系统重磅更新,但“苹果智能”仍与国行无缘

美国西海岸的夏天&#xff0c;再次被苹果点燃。一年一度的全球开发者大会 WWDC25 如期而至&#xff0c;这不仅是开发者的盛宴&#xff0c;更是全球数亿苹果用户翘首以盼的科技春晚。今年&#xff0c;苹果依旧为我们带来了全家桶式的系统更新&#xff0c;包括 iOS 26、iPadOS 26…...

.Net框架,除了EF还有很多很多......

文章目录 1. 引言2. Dapper2.1 概述与设计原理2.2 核心功能与代码示例基本查询多映射查询存储过程调用 2.3 性能优化原理2.4 适用场景 3. NHibernate3.1 概述与架构设计3.2 映射配置示例Fluent映射XML映射 3.3 查询示例HQL查询Criteria APILINQ提供程序 3.4 高级特性3.5 适用场…...

Redis相关知识总结(缓存雪崩,缓存穿透,缓存击穿,Redis实现分布式锁,如何保持数据库和缓存一致)

文章目录 1.什么是Redis&#xff1f;2.为什么要使用redis作为mysql的缓存&#xff1f;3.什么是缓存雪崩、缓存穿透、缓存击穿&#xff1f;3.1缓存雪崩3.1.1 大量缓存同时过期3.1.2 Redis宕机 3.2 缓存击穿3.3 缓存穿透3.4 总结 4. 数据库和缓存如何保持一致性5. Redis实现分布式…...

《从零掌握MIPI CSI-2: 协议精解与FPGA摄像头开发实战》-- CSI-2 协议详细解析 (一)

CSI-2 协议详细解析 (一&#xff09; 1. CSI-2层定义&#xff08;CSI-2 Layer Definitions&#xff09; 分层结构 &#xff1a;CSI-2协议分为6层&#xff1a; 物理层&#xff08;PHY Layer&#xff09; &#xff1a; 定义电气特性、时钟机制和传输介质&#xff08;导线&#…...

解决Ubuntu22.04 VMware失败的问题 ubuntu入门之二十八

现象1 打开VMware失败 Ubuntu升级之后打开VMware上报需要安装vmmon和vmnet&#xff0c;点击确认后如下提示 最终上报fail 解决方法 内核升级导致&#xff0c;需要在新内核下重新下载编译安装 查看版本 $ vmware -v VMware Workstation 17.5.1 build-23298084$ lsb_release…...

微服务商城-商品微服务

数据表 CREATE TABLE product (id bigint(20) UNSIGNED NOT NULL AUTO_INCREMENT COMMENT 商品id,cateid smallint(6) UNSIGNED NOT NULL DEFAULT 0 COMMENT 类别Id,name varchar(100) NOT NULL DEFAULT COMMENT 商品名称,subtitle varchar(200) NOT NULL DEFAULT COMMENT 商…...

【开发技术】.Net使用FFmpeg视频特定帧上绘制内容

目录 一、目的 二、解决方案 2.1 什么是FFmpeg 2.2 FFmpeg主要功能 2.3 使用Xabe.FFmpeg调用FFmpeg功能 2.4 使用 FFmpeg 的 drawbox 滤镜来绘制 ROI 三、总结 一、目的 当前市场上有很多目标检测智能识别的相关算法&#xff0c;当前调用一个医疗行业的AI识别算法后返回…...

基于 TAPD 进行项目管理

起因 自己写了个小工具&#xff0c;仓库用的Github。之前在用markdown进行需求管理&#xff0c;现在随着功能的增加&#xff0c;感觉有点难以管理了&#xff0c;所以用TAPD这个工具进行需求、Bug管理。 操作流程 注册 TAPD&#xff0c;需要提供一个企业名新建一个项目&#…...

如何更改默认 Crontab 编辑器 ?

在 Linux 领域中&#xff0c;crontab 是您可能经常遇到的一个术语。这个实用程序在类 unix 操作系统上可用&#xff0c;用于调度在预定义时间和间隔自动执行的任务。这对管理员和高级用户非常有益&#xff0c;允许他们自动执行各种系统任务。 编辑 Crontab 文件通常使用文本编…...