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

刷题之从前序遍历与中序遍历序列构造二叉树(leetcode)

从前序遍历与中序遍历序列构造二叉树
在这里插入图片描述
前序遍历:中左右
中序遍历:左中右
前序遍历的第一个数必定为根节点,再到中序遍历中找到该数,数的左边是左子树,右边是右子树,进行递归即可。

#include<vector>
using namespace std;struct TreeNode {int val;TreeNode *left;TreeNode *right;TreeNode() : val(0), left(nullptr), right(nullptr) {}TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};class Solution {
private:TreeNode* build(vector<int>& preorder, vector<int>& inorder){if (preorder.size() == 0)return NULL;//找到根节点int rootvalue = preorder[0];TreeNode* root = new TreeNode(rootvalue);//叶子节点if (preorder.size() == 1)return root;//区分左右子树位置int index = 0;for (int i = 0;i < inorder.size();i++){if (inorder[i] == rootvalue){index = i;break;}}vector<int>left_in(inorder.begin(), inorder.begin() + index);vector<int>right_in(inorder.begin() + index + 1, inorder.end());vector<int>left_pre(preorder.begin() + 1, preorder.begin() + 1 + left_in.size());vector<int>right_pre(preorder.begin() + 1 + left_in.size(), preorder.end());root->left = build(left_pre, left_in);root->right = build(right_pre, right_in);return root;}
public:TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {return build(preorder, inorder);}
};int main()
{vector<int> preorder = { 3,9,20,15,7 };vector<int> inorder = { 9,3,15,20,7 };Solution solution;TreeNode* root=solution.buildTree(preorder, inorder);
}

相关文章:

刷题之从前序遍历与中序遍历序列构造二叉树(leetcode)

从前序遍历与中序遍历序列构造二叉树 前序遍历&#xff1a;中左右 中序遍历&#xff1a;左中右 前序遍历的第一个数必定为根节点&#xff0c;再到中序遍历中找到该数&#xff0c;数的左边是左子树&#xff0c;右边是右子树&#xff0c;进行递归即可。 #include<vector>…...

微信小程序--微信开发者工具使用小技巧(3)

一、微信开发者工具使用小技巧 1、快速创建小程序页面 在app.json中的pages配置项&#xff0c;把需要创建的页面填写上去 2、快捷键使用 进入方式 1&#xff1a; 文件–>首选项–> keyboard shortcuts 进入快捷键查看与设置 进入方式 2&#xff1a; 设置–>快捷键…...

JDBC的 PreparedStatement 的用法和解释

文章目录 前言1、封装数据库连接和关闭操作数据库配置文件 config.properties 2、批量添加操作3、查询操作4、修改和删除操作总结 前言 PreparedStatement是预编译的,对于批量处理可以大大提高效率. 也叫JDBC存储过程 1、封装数据库连接和关闭操作 package org.springblade.m…...

LeetCode 面试150

最近准备面试&#xff0c;我以前不愿意面对的 现在保持一颗本心&#xff0c;就是专注于算法思想&#xff0c;语言基础的磨炼&#xff1b; 不为速成&#xff0c;不急功近利的想要比赛&#xff0c;或者为了面试。 单纯的本心&#xff0c;体验算法带来的快乐&#xff0c;是一件非常…...

xmake+xrepo自建仓库添加交叉编译工具链

xmakexrepo自建仓库添加交叉编译工具链 最近想将交叉编译工具链放到xrepo自建仓库中&#xff0c;在xmake中引用&#xff0c;方便多个电脑快速实现交叉编译。 xmake官方文档感觉不够详细&#xff0c;折腾了好久&#xff0c;这里做个记录。 基本步骤如下&#xff1a; 添加自建…...

论文阅读》学习了解自己:一个粗略到精细的个性化对话生成的人物感知训练框架 AAAI 2023

《论文阅读》学习了解自己&#xff1a;一个粗略到精细的个性化对话生成的人物感知训练框架 AAAI 2023 前言 简介研究现状任务定义模型架构Learning to know myselfLearning to avoid Misidentification损失函数实验结果消融实验 前言 亲身阅读感受分享&#xff0c;细节画图解释…...

[Java EE] 网络编程与通信原理(三):网络编程Socket套接字(TCP协议)

&#x1f338;个人主页:https://blog.csdn.net/2301_80050796?spm1000.2115.3001.5343 &#x1f3f5;️热门专栏:&#x1f355; Collection与数据结构 (92平均质量分)https://blog.csdn.net/2301_80050796/category_12621348.html?spm1001.2014.3001.5482 &#x1f9c0;Java …...

MyBatis懒加载数据(大批量数据处理)

使用范例 Cursor约定使用Iterator去懒加载数据&#xff0c;以时间换空间&#xff0c;非常适合处理通常无法容纳在内存中的数百万个项目查询。如果在 resultMap 中使用集合&#xff0c;则必须使用 resultMap 的 id 列对游标 SQL 查询进行排序(resultOrdered“true”)。 //为了避…...

MySQL--联合索引应用细节应用规范

目录 一、索引覆盖 1.完全覆盖 2.部分覆盖 3.不覆盖索引-where条件不包含联合索引的最左则不覆盖 二、MySQL8.0在索引中的新特性 1.不可见索引 2.倒序索引 三、索引自优化--索引的索引 四、Change Buffer 五、优化器算法 1.查询优化器算法 2.设置算法 3.索引下推 …...

【spring boot+Lazy ORM+mysql】开发一个数据库管理系统实现对应数据库数据查看和修改

【spring bootLazy ORMmysql】开发一个数据库管理系统实现对应数据库数据查看和修改 演示项目地址&#xff1a;http://124.222.48.62:30193/wu-smart-acw-ui/index.html#/login &#xff08;admin/admin&#xff09; 功能 用户登录注册新增、编辑数实例新增、编辑数据库信息…...

知识分享:隔多久查询一次网贷大数据信用报告比较好?

随着互联网金融的快速发展&#xff0c;越来越多的人开始接触和使用网络贷款。而在这个过程中&#xff0c;网贷大数据信用报告成为了评估借款人信用状况的重要依据。那么&#xff0c;隔多久查询一次网贷大数据信用报告比较好呢?接下来随小易大数据平台小编去看看吧。 首先&…...

【Day8:JAVA字符串的学习】

目录 1、常用API2、String类2.1 String类的特点2.2 String类的常见构造方法2.3 String类的常见面试题&#xff1a;2.3.1 面试题一&#xff1a;2.3.2 面试题二&#xff1a;2.3.3 面试题三&#xff1a;2.3.4 面试题四&#xff1a; 2.4 String类字符串用于比较的方法2.5 String类字…...

jetcache缓存

1 介绍 是阿里的双极缓存&#xff0c;jvm-->redis-->数据库 文档&#xff1a;jetcache/docs/CN at master alibaba/jetcache GitHub 2 注意事项 使用的实体类一定实现序列化接口定时刷新注解&#xff0c;慎用 它会为每一个key创建一个定时器 &#xff1a;场景为&…...

SQLSyntaxErrorException: FUNCTION dbname.to_timestamp does not exist

由于MySQL数据库高版本&#xff08;如8.x&#xff09;中有to_timestamp(&#xff09;函数&#xff0c;低版本中&#xff08;如5.7.x&#xff09;没有这个函数&#xff0c;服务运行报错。 自己创建函数实现功能&#xff0c;创建语句如下&#xff1b; DELIMITER // CREATE FUN…...

Borel-Cantelli 引理

翻译自大佬 https://huarui1998.com/Notes/math/borel-cantelli.html 1. 集序列的 lim ⁡ inf ⁡ \lim\inf liminf 和 lim ⁡ sup ⁡ \lim\sup limsup 类似于定义实数序列 { a k } \{a_k\} {ak​} 的 lim ⁡ inf ⁡ \lim\inf liminf 和 lim ⁡ sup ⁡ \lim\sup limsup, …...

算法训练营第四十一天 | LeetCode 509 斐波那契数列、LeetCode 70 爬楼梯、LeetCode 746 使用最小花费爬楼梯

LeetCode 509 斐波那契数列 这题动规五部曲都定义得比较明确。首先是dp数组下标&#xff0c;题目中给定F(0) 0说明从0开始&#xff0c;dp[i]直接表示F(i)的值即可。递推公式也直接给出了&#xff0c;也给了开头两个作为递推基础的数值作为初始化依据。遍历顺序也指明是从前往…...

网络其他重要协议(DNS、ICMP、NAT)

1.DNS DNS是一整套从域名映射到IP的系统 1.1 DNS背景 TCP/IP中使用IP地址和端口号来确定网络上的一台主机的一个程序&#xff0c;但是IP地址不方便记忆&#xff0c;例如我们想访问百度就会在浏览器中输入baidu.com而不是百度的IP地址。于是人们发明了一种叫主机名的东西, 是…...

利用PyCSP3库(含大量全局约束)进行组合约束建模

文章目录 1. 什么是 PyCSP3 ?2. 安装方法(Windows)2.1 通过 Google_colab 直接运行2.2 通过 pip 进行安装3. 快速入门3.1 声明变量3.2 更新约束3.3 定义目标3.4 常用的全局约束1. 什么是 PyCSP3 ? PyCSP3 是 Python 中的一个库,用于对组合约束问题进行建模,包括 约束满足…...

解决updateByExample时属性值异常的问题(部分属性值没有使用占位符?进行占位,而是变成了属性的名称)

目录 场景简介代码片断实体类 报错信息排查原因解决测试过程解决方案 场景简介 1、程序将mybatis框架升级为3.5.9版本后执行updateByExample方法时报错 代码片断 Condition condition new Condition(MbCcsSessionConfig.class); condition.createCriteria().andEqualTo(&quo…...

[C++][algorithm][Eigen] 基于Eigen实现Softmax函数

1 简介 Softmax函数是机器学习和深度学习中一个非常重要的激活函数&#xff0c;它在多分类问题中尤其关键。Softmax函数能够将一个向量或一组实数转换成概率分布&#xff0c;使得每个元素的值都在0到1之间&#xff0c;并且所有元素的和为1。本博客文章《【Eigen】基于Eigen实现…...

Chapter03-Authentication vulnerabilities

文章目录 1. 身份验证简介1.1 What is authentication1.2 difference between authentication and authorization1.3 身份验证机制失效的原因1.4 身份验证机制失效的影响 2. 基于登录功能的漏洞2.1 密码爆破2.2 用户名枚举2.3 有缺陷的暴力破解防护2.3.1 如果用户登录尝试失败次…...

2025年能源电力系统与流体力学国际会议 (EPSFD 2025)

2025年能源电力系统与流体力学国际会议&#xff08;EPSFD 2025&#xff09;将于本年度在美丽的杭州盛大召开。作为全球能源、电力系统以及流体力学领域的顶级盛会&#xff0c;EPSFD 2025旨在为来自世界各地的科学家、工程师和研究人员提供一个展示最新研究成果、分享实践经验及…...

从零实现富文本编辑器#5-编辑器选区模型的状态结构表达

先前我们总结了浏览器选区模型的交互策略&#xff0c;并且实现了基本的选区操作&#xff0c;还调研了自绘选区的实现。那么相对的&#xff0c;我们还需要设计编辑器的选区表达&#xff0c;也可以称为模型选区。编辑器中应用变更时的操作范围&#xff0c;就是以模型选区为基准来…...

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

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

Module Federation 和 Native Federation 的比较

前言 Module Federation 是 Webpack 5 引入的微前端架构方案&#xff0c;允许不同独立构建的应用在运行时动态共享模块。 Native Federation 是 Angular 官方基于 Module Federation 理念实现的专为 Angular 优化的微前端方案。 概念解析 Module Federation (模块联邦) Modul…...

vue3+vite项目中使用.env文件环境变量方法

vue3vite项目中使用.env文件环境变量方法 .env文件作用命名规则常用的配置项示例使用方法注意事项在vite.config.js文件中读取环境变量方法 .env文件作用 .env 文件用于定义环境变量&#xff0c;这些变量可以在项目中通过 import.meta.env 进行访问。Vite 会自动加载这些环境变…...

从 GreenPlum 到镜舟数据库:杭银消费金融湖仓一体转型实践

作者&#xff1a;吴岐诗&#xff0c;杭银消费金融大数据应用开发工程师 本文整理自杭银消费金融大数据应用开发工程师在StarRocks Summit Asia 2024的分享 引言&#xff1a;融合数据湖与数仓的创新之路 在数字金融时代&#xff0c;数据已成为金融机构的核心竞争力。杭银消费金…...

Web后端基础(基础知识)

BS架构&#xff1a;Browser/Server&#xff0c;浏览器/服务器架构模式。客户端只需要浏览器&#xff0c;应用程序的逻辑和数据都存储在服务端。 优点&#xff1a;维护方便缺点&#xff1a;体验一般 CS架构&#xff1a;Client/Server&#xff0c;客户端/服务器架构模式。需要单独…...

libfmt: 现代C++的格式化工具库介绍与酷炫功能

libfmt: 现代C的格式化工具库介绍与酷炫功能 libfmt 是一个开源的C格式化库&#xff0c;提供了高效、安全的文本格式化功能&#xff0c;是C20中引入的std::format的基础实现。它比传统的printf和iostream更安全、更灵活、性能更好。 基本介绍 主要特点 类型安全&#xff1a…...

MySQL 主从同步异常处理

阅读原文&#xff1a;https://www.xiaozaoshu.top/articles/mysql-m-s-update-pk MySQL 做双主&#xff0c;遇到的这个错误&#xff1a; Could not execute Update_rows event on table ... Error_code: 1032是 MySQL 主从复制时的经典错误之一&#xff0c;通常表示&#xff…...