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

【剑指Offer】重建二叉树(递归+迭代)

重建二叉树

  • 一、递归法
  • 二、迭代法

题目链接

题目描述:
输入某二叉树的前序遍历和中序遍历的结果,请构建该二叉树并返回其根节点。
假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

示例 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]

一、递归法

首先我们知道中序的左边就是该节点的左子树,中序的右边就是该节点的右子树,而确认根的顺序就需要靠前序。
在这里插入图片描述
所以我们可以用一个变量pi记录前序遍历的位置,在中序中找到相同的元素,然后把它的左右区间递归下去。
这里注意如果要每次递归都需要遍历中序找到根,时间复杂度过高,所以我们可以在递归前先用哈希表映射根的位置

代码如下

class Solution {
public:unordered_map<int, int> index;TreeNode* _bulidTree(vector<int>& pre, vector<int>& in, int& pi, int begin, int end){if (begin > end) return nullptr;int mid = index[pre[pi]];TreeNode* root = new TreeNode(pre[pi++]);root->left = _bulidTree(pre, in, pi, begin, mid - 1);root->right = _bulidTree(pre, in, pi, mid + 1, end);return root;}TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {int pi = 0;for (int i = 0; i < preorder.size(); i++){index[inorder[i]] = i;}return _bulidTree(preorder, inorder, pi, 0, preorder.size() - 1);}
};

二、迭代法

三种顺序的迭代法遍历:【数据结构】二叉树的非递归遍历

我们先假象一种情况,一棵树只有左子树的话,那么就相当于是一个单链表,那么它的前序遍历和中序遍历就刚好是反过来的。那么我们就可以使用栈来逆序存放,一旦遍历到最左下节点,这时候就该返回,开始弹栈,当我们发现弹栈的顺序和中序遍历不一致的时候,说明最后一个弹出来的节点有右子树
在这里插入图片描述
可以发现前序走完后出栈顺序刚好是中序遍历的结果,所以没有右子树。

在这里插入图片描述在这里插入图片描述
代码如下:

class Solution {
public:TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {if(preorder.empty()) return nullptr;stack<TreeNode*> st;int inorIndex = 0;TreeNode* root = new TreeNode(preorder[0]);st.push(root);for(int i = 1; i < preorder.size(); i++){TreeNode* node = st.top();if(node->val != inorder[inorIndex]){node->left = new TreeNode(preorder[i]);st.push(node->left);}else{while(!st.empty() && st.top()->val == inorder[inorIndex]){node = st.top();st.pop();inorIndex++;}node->right = new TreeNode(preorder[i]);st.push(node->right);}}return root;}
};

相关文章:

【剑指Offer】重建二叉树(递归+迭代)

重建二叉树一、递归法二、迭代法题目链接 题目描述&#xff1a; 输入某二叉树的前序遍历和中序遍历的结果&#xff0c;请构建该二叉树并返回其根节点。 假设输入的前序遍历和中序遍历的结果中都不含重复的数字。 示例 1: Input: preorder [3,9,20,15,7], inorder [9,3,15,…...

注解@Transactional 原理和常见的坑

这篇文章&#xff0c;会先讲述 Transactional 的 4 种不生效的 Case&#xff0c;然后再通过源码解读&#xff0c;分析 Transactional 的执行原理&#xff0c;以及部分 Case 不生效的真正原因1 项目准备下面是 DB 数据和 DB 操作接口&#xff1a;uidunameusex1张三女2陈恒男3楼仔…...

2023年全国最新交安安全员精选真题及答案4

百分百题库提供交安安全员考试试题、交安安全员考试预测题、交安安全员考试真题、交安安全员证考试题库等&#xff0c;提供在线做题刷题&#xff0c;在线模拟考试&#xff0c;助你考试轻松过关。 31.特种劳动防护用品必须具有“三证”&#xff0c;下列不属于“三证”的是&#…...

扬帆优配|半天翻倍,“蹭热点”翻车,前期“牛股”已近腰斩

周五上午&#xff0c;A股商场整体走低&#xff0c;多数职业板块和个股跌落&#xff0c;军工和核算机等板块逆势上涨&#xff0c;北向资金半天净卖出额约38亿元。 个股方面&#xff0c;昨夜公告被证监会立案查询的奥联电子股价再度大跌&#xff0c;盘中最贱价较近期高位已腰斩。…...

6 种易于上手的编程副业,每月赚取 1,000 多美元——没有废话

没有自由职业者或博客&#xff0c;也不需要前期费用。你们中的大多数人阅读这样的故事是希望其中的一些故事能帮助您赚更多的钱。好吧&#xff0c;几年前我还是同一个人。我希望尝试一些新的副业并赚点钱。其中一个视频建议我在网上写作&#xff0c;此后我写了很多技术文章。在…...

第九届蓝桥杯省赛 C++ B组 - 日志统计

✍个人博客&#xff1a;https://blog.csdn.net/Newin2020?spm1011.2415.3001.5343 &#x1f4da;专栏地址&#xff1a;蓝桥杯题解集合 &#x1f4dd;原题地址&#xff1a;日志统计 &#x1f4e3;专栏定位&#xff1a;为想参加蓝桥杯的小伙伴整理常考算法题解&#xff0c;祝大家…...

记一次服务器入侵事件的应急响应

0x01 事件背景 8月某日&#xff0c;客户官网被黑&#xff0c;需在特定时间内完成整改。为避免客户业务受到影响&#xff0c;实验室相关人员第一时间展开本次攻击事件的应急处理。 0x02 事件分析 网站源码被篡改&#xff0c;攻击者一定获取到了权限&#xff0c;那么接下来的思…...

作用域链查找机制(回顾)

全局 / 私有变量作用域的概念作用域链 scopeChain 的概念作用域链 scopeChain 的形成函数执行步骤作用域链查找机制 全局 / 私有变量 全局变量&#xff1a;在全局上下文EC(G)中的全局变量对象VO(G)中,存储的变量 私有变量&#xff1a;在函数执行形成的私有上下文EC(XXX)中的变…...

前端基础之HTML扫盲

文章目录一. 第一个HTML程序1. 创建一个HTML文件并运行2. HTML的基本结构二. HTML常见标签1. 注释标签2. 标题标签3. 段落标签4. 换行标签5. 格式化标签6. 图片标签7. 超链接标签8. 表格标签9. 列表标签10. 表单标签10.1 input标签10.2 select标签10.3 textarea标签11. 无语义标…...

大规模食品图像识别:T-PAMI 2023论文解读

美团基础研发平台视觉智能部与中科院计算所展开科研课题合作&#xff0c;共同构建大规模数据集Food2K&#xff0c;并提出渐进式区域增强网络用于食品图像识别&#xff0c;相关研究成果已发表于T-PAMI 2023。本文主要介绍了数据集特点、方法设计、性能对比&#xff0c;以及基于该…...

【java】Spring Cloud --Spring Cloud Alibaba RocketMq 异步通信实现

文章目录介绍RocketMQ特点Spring Cloud StreamWindow搭建部署RocketMQ下载启动NameServer服务启动Broker服务示例创建 RocketMQ 消息生产者创建 RocketMQ 消息消费者使用示例示例关联项目运行示例测试介绍 RocketMQ 是一款开源的分布式消息系统&#xff0c;基于高可用分布式集…...

玫瑰花变蚊子血,自动化无痕浏览器对比测试,新贵PlayWright Vs 老牌Selenium,基于Python3.10

也许每一个男子全都有过这样的两个女人&#xff0c;至少两个。娶了红玫瑰&#xff0c;久而久之&#xff0c;红的变了墙上的一抹蚊子血&#xff0c;白的还是床前明月光&#xff1b;娶了白玫瑰&#xff0c;白的便是衣服上沾的一粒饭黏子&#xff0c;红的却是心口上一颗朱砂痣。–…...

Spring Cloud入门篇 Hello World | Spring Cloud 1

一、专栏说明 Spring Cloud是一系列框架的有序集合。它利用Spring Boot的开发便利性巧妙地简化了分布式系统基础设施的开发,如:服务发现/注册、配置中心、消息总线、负载均衡、断路器、数据监控等,都可以用Spring Boot的开发风格做到一键启动和部署。 本文主要介绍Spring C…...

C++学习笔记-数据结构

结构 是C中另一种用户自定义的可用数据类型&#xff0c;允许存储不同类型的数据项。 C/C 数组允许定义可存储相同类型数据项的变量&#xff0c;但是结构是 C 中另一种用户自定义的可用的数据类型&#xff0c;它允许存储不同类型的数据项。 结构用于表示一条记录&#xff0c;假…...

【C++的OpenCV】第五课-OpenCV图像常用操作(二):OpenCV的基本绘图、平滑滤波(模糊)处理

让我们继续一、OpenCV基本绘图1.1 OpenCV关于绘图的操作1.1.1 cv::Point()1.1.2 cv::Scalar()1.1.3 cv::line()画线1.1.4 cv::rectangle()画矩形1.1.5 cv::circle()画圆二、图像的平滑滤波处理2.1 概念2.2 OpenCV关于图像模糊的操作2.2.1 常用滤波器的分类2.2.2 各种滤波方法具…...

[SSD固态硬盘技术 19] 谁是数据的守护神? 盘内RAID1/RAID5图文详解_盘内数据冗余保护

版权声明&#xff1a; 付费作品&#xff0c;禁止转载前言提到冗余保护&#xff0c;最容易想到的就是RAID(Redundant Arrays of Independent Disks) , 独立冗余磁盘阵列。它是一种把多块独立的物理硬盘按不同方式组合形成一个硬盘组&#xff0c;以此提供比单个硬盘更高的存储性能…...

linux相对于windows环境为啥相对来说更加具有安全性

linux相对于windows环境为啥相对来说更加具有安全性 文章目录linux相对于windows环境为啥相对来说更加具有安全性前言一、linux不需要防病毒软件1.1Linux 桌面的恶意软件很少见1.2Linux 的软件安装更安全1.3Linux 保护自己免受恶意软件的侵害1.4杀毒效果存疑1.5Linux 良好的安全…...

iOS开发笔记之九十七——关于Restful API的一些总结

*****阅读完此文&#xff0c;大概需要3分钟******一、什么是 Restful API&#xff1f;Restful&#xff08;Representational State Transfer表现层状态转换&#xff09;是目前最流行的接口设计规范。Restful API 是一种设计风格&#xff08;是设计风格而不是标准&#xff09;&a…...

Linux系统Nginx下载和安装

文章目录golang学习面试网站Linux启动nginx参考Linux启动nginx版权声明&#xff1a;本文为博主原创文章&#xff0c;遵循 CC 4.0 BY-SA 版权协议&#xff0c;转载请附上原文出处链接和本声明。 本文链接&#xff1a;https://blog.csdn.net/weixin_36755535/article/details/110…...

交叉编译 acl

交叉编译 acl 概述 访问控制列表&#xff08;Access Control Lists&#xff0c;ACL&#xff09;是应用在路由器接口的指令列表。在 Linux 系统中&#xff0c;ACL 用于设定用户针对文件的权限&#xff0c;而不是在交换路由器中用来控制数据访问的功能&#xff08;类似于防火墙…...

第19节 Node.js Express 框架

Express 是一个为Node.js设计的web开发框架&#xff0c;它基于nodejs平台。 Express 简介 Express是一个简洁而灵活的node.js Web应用框架, 提供了一系列强大特性帮助你创建各种Web应用&#xff0c;和丰富的HTTP工具。 使用Express可以快速地搭建一个完整功能的网站。 Expre…...

设计模式和设计原则回顾

设计模式和设计原则回顾 23种设计模式是设计原则的完美体现,设计原则设计原则是设计模式的理论基石, 设计模式 在经典的设计模式分类中(如《设计模式:可复用面向对象软件的基础》一书中),总共有23种设计模式,分为三大类: 一、创建型模式(5种) 1. 单例模式(Sing…...

2025 后端自学UNIAPP【项目实战:旅游项目】6、我的收藏页面

代码框架视图 1、先添加一个获取收藏景点的列表请求 【在文件my_api.js文件中添加】 // 引入公共的请求封装 import http from ./my_http.js// 登录接口&#xff08;适配服务端返回 Token&#xff09; export const login async (code, avatar) > {const res await http…...

成都鼎讯硬核科技!雷达目标与干扰模拟器,以卓越性能制胜电磁频谱战

在现代战争中&#xff0c;电磁频谱已成为继陆、海、空、天之后的 “第五维战场”&#xff0c;雷达作为电磁频谱领域的关键装备&#xff0c;其干扰与抗干扰能力的较量&#xff0c;直接影响着战争的胜负走向。由成都鼎讯科技匠心打造的雷达目标与干扰模拟器&#xff0c;凭借数字射…...

《C++ 模板》

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

算法:模拟

1.替换所有的问号 1576. 替换所有的问号 - 力扣&#xff08;LeetCode&#xff09; ​遍历字符串​&#xff1a;通过外层循环逐一检查每个字符。​遇到 ? 时处理​&#xff1a; 内层循环遍历小写字母&#xff08;a 到 z&#xff09;。对每个字母检查是否满足&#xff1a; ​与…...

Go 语言并发编程基础:无缓冲与有缓冲通道

在上一章节中&#xff0c;我们了解了 Channel 的基本用法。本章将重点分析 Go 中通道的两种类型 —— 无缓冲通道与有缓冲通道&#xff0c;它们在并发编程中各具特点和应用场景。 一、通道的基本分类 类型定义形式特点无缓冲通道make(chan T)发送和接收都必须准备好&#xff0…...

抽象类和接口(全)

一、抽象类 1.概念&#xff1a;如果⼀个类中没有包含⾜够的信息来描绘⼀个具体的对象&#xff0c;这样的类就是抽象类。 像是没有实际⼯作的⽅法,我们可以把它设计成⼀个抽象⽅法&#xff0c;包含抽象⽅法的类我们称为抽象类。 2.语法 在Java中&#xff0c;⼀个类如果被 abs…...

渗透实战PortSwigger靶场:lab13存储型DOM XSS详解

进来是需要留言的&#xff0c;先用做简单的 html 标签测试 发现面的</h1>不见了 数据包中找到了一个loadCommentsWithVulnerableEscapeHtml.js 他是把用户输入的<>进行 html 编码&#xff0c;输入的<>当成字符串处理回显到页面中&#xff0c;看来只是把用户输…...

绕过 Xcode?使用 Appuploader和主流工具实现 iOS 上架自动化

iOS 应用的发布流程一直是开发链路中最“苹果味”的环节&#xff1a;强依赖 Xcode、必须使用 macOS、各种证书和描述文件配置……对很多跨平台开发者来说&#xff0c;这一套流程并不友好。 特别是当你的项目主要在 Windows 或 Linux 下开发&#xff08;例如 Flutter、React Na…...