day24-106.从中序与后序遍历序列构造二叉树

106.从中序与后序遍历序列构造二叉树

力扣题目链接(opens new window)

根据一棵树的中序遍历与后序遍历构造二叉树。

注意: 你可以假设树中没有重复的元素。

例如,给出

  • 中序遍历 inorder = [9,3,15,20,7]
  • 后序遍历 postorder = [9,15,7,20,3] 返回如下的二叉树:

106. 从中序与后序遍历序列构造二叉树1

思路

根据中序遍历和后序遍历构造二叉树的理论知识:首先由后序遍历确定根节点(从尾开始遍历),在中序遍历找到其相应的左右子节点(左中右),反复这个操作。

根据理论知识我们转换成实际操作。

  • 取Postorder的最后一个元素
    • 若Postorder的数组为空,则返回null
  • 确定根元素在Inorder中的位置
  • 开始分割
    • 先分割中序
      • 左毕右开
    • 后分割后序
      • 左闭右开
  • 递归
  • 返回

代码如下:

class Solution {
public:TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {if(postorder.empty())return nullptr;// 当前根节点int rootValue = postorder[postorder.size()-1];TreeNode* root = new TreeNode(rootValue);// 找根节点在中序的位置int deliIndex;for(deliIndex = 0;deliIndex<inorder.size();deliIndex++){if(inorder[deliIndex] == rootValue)break;}//分割中序左右子结点vector<int> leftInorder(inorder.begin(),inorder.begin() + deliIndex);vector<int> rightInoder(inorder.begin() + deliIndex + 1, inorder.end());//分割前序左右子节点postorder.resize(postorder.size()-1);vector<int> leftPostorder(postorder.begin(), postorder.begin() + leftInorder.size());vector<int> rightPostorder(postorder.begin() + leftInorder.size(), postorder.end());root->left = buildTree(leftInorder,leftPostorder);root->right = buildTree(rightInoder,rightPostorder);return root;}
};

Tips:切割后序数组的时候,可以根据中序分割的大小进行分割,因为其大小一定是一致的。

优化

第一个优化:在找根节点分别在后序和中序中的位置时,可以使用map进行编号。

第二个优化:进行分割时,只需分割中序数组即可。

class Solution {
private:int cus_pos;unordered_map<int,int>in;
public:TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {cus_pos=postorder.size()-1;int num=0;// 对inorder进行编号for(auto &n:inorder){in[n]=num++;}int left=0,right=inorder.size()-1;return dis(left,right,inorder,postorder);}TreeNode* dis(int left,int right,vector<int>& inorder, vector<int>& postorder){if(left>right)return nullptr;int root_val=postorder[cus_pos--];int index=in[root_val];TreeNode* p=new TreeNode(root_val);// 分割数组p->right=dis(index+1,right,inorder,postorder);p->left=dis(left,index-1,inorder,postorder);return p;}
};r,postorder);p->left=dis(left,index-1,inorder,postorder);return p;}
};

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

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

相关文章

如何在win10系统上使用旧版本的IE浏览器

win10系统打开IE浏览器自动变成了Edge浏览器&#xff0c;切换成IE模式时&#xff0c;IE浏览器的版本默认为IE11&#xff08;注&#xff1a;Edge浏览器只支持IE11&#xff09;&#xff0c;有些网站只能使用IE浏览器打开或者在做一些兼容性测试时&#xff0c;需要使用到不同版本的…

PLC求解弹簧质量模型微分方程数值解(RK4梯形图程序)

微分方程的数值求解,属于数学分析类课程涉及的内容。大家可以参看相关书籍对Runge-Kutta法的介绍,弹簧质量阻尼模型详细的微分方程介绍可以查看下面文章,链接如下: 弹簧质量阻尼系统前馈PID位置控制(PLC闭环仿真SCL+ST代码)_RXXW_Dor的博客-CSDN博客带前馈控制的博途PID程…

【数据结构•堆】堆排序(理论基础)

堆的定义  • 堆是一个完全二叉树   –所有叶子在同一层或者两个连续层   –最后一层的结点占据尽量左的位置  • 堆性质   –为空, 或者最小元素在根上   –两棵子树也是堆 存储方式  • 最小堆的元素保存在heap[1..hs]内   – 根在heap[1]   –K的左儿子是2k,…

在线吉他调音

先看效果&#xff08;图片没有声&#xff0c;可以下载源码看看&#xff0c;比这更好~&#xff09;&#xff1a; 再看代码&#xff08;查看更多&#xff09;&#xff1a; <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8&quo…

【Unity】VS Code 没有智能提示 Unity 中的类

正常来说&#xff0c;VS Code中会对部分输入类名进行提示&#xff0c;如下图所述 假如你从Unity 中进入 VS Code后发现没有提示相关 Unity的类&#xff0c;可能是 Unity 中 有关于 VS Code的相关Package 没有跟着 VS Code升级到最新版本。 点击Unity Windows 下拉框中的 Pac…

基于Promise.resolve实现Koa请求队列中间件

本文作者为360奇舞团前端工程师 前言 最近在做一个 AIGC 项目&#xff0c;后端基于 Koa2 实现。其中有一个需求就是调用兄弟业务线服务端 AIGC 能力生成图片。但由于目前兄弟业务线的 AIGC 项目也是处于测试阶段&#xff0c;能够提供的服务器资源有限&#xff0c;当并发请求资源…

直播带货热潮:海外网红直播对产品推广的影响与机遇

随着互联网的快速发展和社交媒体的普及&#xff0c;直播带货成为了一种风靡全球的新型营销方式。其中&#xff0c;海外网红直播作为直播带货的一种形式&#xff0c;引起了广泛的关注。海外网红以其独特的个人魅力和粉丝基础&#xff0c;成为了产品推广的强有力渠道。本文Nox聚星…

SpringBoot 异步、邮件任务

异步任务 创建一个Hello项目 创建一个类AsyncService 异步处理还是非常常用的&#xff0c;比如我们在网站上发送邮件&#xff0c;后台会去发送邮件&#xff0c;此时前台会造成响应不动&#xff0c;直到邮件发送完毕&#xff0c;响应才会成功&#xff0c;所以我们一般会采用多线…

JVM 调优实例

点击下方关注我&#xff0c;然后右上角点击...“设为星标”&#xff0c;就能第一时间收到更新推送啦~~~ JVM提供了多种垃圾回收器&#xff0c;可以根据应用程序的需求选择最适合的垃圾回收器。例如&#xff0c;如果应用程序需要更快的响应时间&#xff0c;可以选择并行垃圾回收…

从源代码编译构建Apach Spark3.2.4

从源代码编译构建Apach Spark3.2.4 编译说明编译Apache Spark下载源码构建环境准备使用本地Maven构建更改Scala版本下载Jar包构建可运行的发行版构建异常构建成功 运行测试 编译说明 对于大多数用户来说&#xff0c;使用官方预编译版本的Spark已经足够满足日常需求。只有在特定…

FFmpeg常见命令行(四):FFmpeg流媒体

前言 在Android音视频开发中&#xff0c;网上知识点过于零碎&#xff0c;自学起来难度非常大&#xff0c;不过音视频大牛Jhuster提出了《Android 音视频从入门到提高 - 任务列表》&#xff0c;结合我自己的工作学习经历&#xff0c;我准备写一个音视频系列blog。本文是音视频系…

10.Eclipse配置Tomcat详细教程、如何使用Eclipse+tomcat创建并运行web项目

一、Tomcat的下载官网 -> 进入官网显示如图所示的界面&#xff0c;在下下载的是Tomcat9.0版本&#xff0c;你可以自己选一款 点击然后进入下面这个界面 最好是在你的D盘建立一个文件夹&#xff0c;把它解压在里面&#xff0c;文件夹名自己来吧&#xff0c;自己能知道里面装…

使用基于jvm-sandbox的对三层嵌套类型的改造

使用基于jvm-sandbox的对三层嵌套类型的改造 问题背景 先简单介绍下基于jvm-sandbox的imock工具&#xff0c;是Java方法级别的mock&#xff0c;操作就是监听指定方法&#xff0c;返回指定的mock内容。 jvm-sandbox 利用字节码操作和自定义类加载器的技术&#xff0c;将原始方法…

【jvm】类加载子系统

目录 一、图二、类加载器作用三、类加载器角色四、类的加载过程4.1 加载4.1.1 说明4.1.2 加载.class文件的方式 4.2 链接4.2.1 验证(verify [ˈverɪfaɪ])4.2.2 准备(prepare)4.2.3 解析(resolve) 4.3 初始化4.3.1 说明4.3.2 图示14.3.3 图示24.3.3 图示3 一、图 二、类加载器…

解密Flink的状态管理:探索流处理框架的数据保留之道,释放流处理的无限潜能!

水善利万物而不争&#xff0c;处众人之所恶&#xff0c;故几于道&#x1f4a6; 文章目录 一、什么是状态二、应用场景三、Flink中状态的分类四、算子状态1. 列表状态&#xff08;List State&#xff09;2. 广播状态&#xff08;Broadcast State&#xff09; 五、键控状态1. Val…

股票指数——RSI指数

RSI指数的计算非常简单&#xff0c;就是使用一段时间内的平均上涨除以平均上涨加平均下跌&#xff08;取正值&#xff09;。也就意味着RSI指数的取值是[0,100]之间&#xff0c;其中0表示周期内没有上涨的&#xff0c;100表示周期内没有下跌的。RSI的直观意义是它表示了一段周期…

用神经网络玩转数据聚类:自编码器的原理与实践

目录 引言一、什么是自编码器二、自编码器的应用场景三、自编码器的优缺点四、如何实现基于自编码器的聚类算法五、总结 引言 随着数据量的爆炸性增长&#xff0c;如何有效地处理和分析数据成为了一个重要的问题。数据聚类是一种常用的数据分析方法&#xff0c;它可以将数据集…

gateway做token校验

本文使用springcloud的gateway做token校验 登录的本质&#xff1a;拿用户名和密码 换 token。 token会返回给浏览器&#xff08;存储&#xff09;&#xff0c;当访问的时候&#xff0c;携带token 发起请求。 token校验图 引入redis依赖 <dependency><groupId>or…

codeforces代:

感受思维的美丽&#xff0c;abcde题目的思路是怎么样的&#xff1a; 上蓝 上紫 可以代 &#xff1a;有问题可以评论区 直接问我 也可以q: 639682754

Django入门

Day1 django环境安装 创建虚拟环境 # step1 创建虚拟环境 python3 -m venv datawhale_django # step2 mac进入虚拟环境 source ./datawhale_django/bin/activate # step3 退出虚拟环境 deactivate安装包 pip3 install django ​pip3 install djangorestframework​​ pip3 …