★【递归】【构造二叉树】Leetcode 106.从中序与后序遍历序列构造二叉树
★【递归前序】【构造二叉树】Leetcode 106.从中序与后序遍历序列构造二叉树 105. 从前序与中序遍历序列构造二叉树
- 106.从中序与后序遍历序列构造二叉树
- :star:思路分析
- 递归解法
- 105. 从前序与中序遍历序列构造二叉树
- 递归解法
凡是构造二叉树>>>>>>>>>>前序遍历(中左右)
---------------🎈🎈题目链接🎈🎈-------------------
106.从中序与后序遍历序列构造二叉树

⭐️思路分析
后序数组: 左 右 中
中序数组: 左 中 右
以后序数组的最后一个元素(即为根节点)为切割点,先切中序数组,
再根据中序数组的左长度,反过来再切后序数组的左和右。
一层一层切下去,每次后序数组最后一个元素就是节点元素。

递归解法

⭐️⭐️⭐️⭐️⭐️⭐️
1. 如果数组大小为0,说明是空节点,return null
2. 如果不为空,那么取后序数组的最后一个节点
3. 找到后序数组最后一个节点 在中序数组中的位置 作为切割点
4. 切割中序数组,切成中序左数组 和 中序右数组
5. 根据中序左数组的长度,切割后序数组,切成后序左数组和后序右数组
6. 递归处理左区间和右区间
时间复杂度O(N)
空间复杂度O(N)
采用了【左闭右闭】——只要一直保持一致就行
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val = val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val = val;* this.left = left;* this.right = right;* }* }*/
class Solution {public TreeNode buildTree(int[] inorder, int[] postorder) {//1.如果数组为空 那么就返回nullif(inorder.length ==0 || postorder.length==0){return null;}return helper(inorder, postorder, 0, inorder.length-1, 0,postorder.length-1);//}public TreeNode helper(int[] inorder, int[] postorder, int inorderBegin, int inorderEnd, int postorderBegin, int postorderEnd){if(postorderBegin > postorderEnd){return null;}// 采用左闭右闭//2.如果不为空, 那么就取后序数组的最后一个元素int rootval = postorder[postorderEnd];TreeNode root= new TreeNode(rootval);//3.切割中序数组 得到对应中序数组中rootval所在的位置 进而得到中序左数组 中序右数组int midIndex;for(midIndex = inorderBegin; midIndex<=inorderEnd; midIndex++){if(inorder[midIndex] == rootval){break;}}int leftInorderBegin = inorderBegin; // 中序左数组开头int leftInorderEnd = midIndex-1; // 中序左数组结尾int rightInorderBegin = midIndex+1; // 中序右数组开头int rightInorderEnd = inorderEnd; // 中序右数组结尾//4.根据中序左数组 切割后序数组,得到后序左数组 后序右数组int leftPostorderBegin = postorderBegin; // 后序左数组开头int leftPostorderEnd = postorderBegin + midIndex -inorderBegin -1; // 后序左数组结尾int rightPostorderBegin = leftPostorderEnd+1; // 后序右数组开头int rightPostorderEnd = postorderEnd-1; // 后序右数组结尾//5.递归处理左子树和右子树root.left = helper(inorder, postorder, leftInorderBegin, leftInorderEnd, leftPostorderBegin, leftPostorderEnd);root.right = helper(inorder, postorder, rightInorderBegin, rightInorderEnd, rightPostorderBegin, rightPostorderEnd);return root;}
}
105. 从前序与中序遍历序列构造二叉树
递归解法
⭐️⭐️⭐️⭐️⭐️⭐️
接受参数int[ ] preorder, int[ ] inorder, preorder的开始,preorder的结束,inorder的开始,inorder的结束
1. 如果数组大小为0,说明是空节点,return null
2. 从前序的第一个得到根节点root
3. 根据midval 在中序数组inorder中 寻找切割点midindex
4. 对中序数组inorder进行切割 :中序左(begin/end) 中序右(begin/end)
5. 根据分化结果,对前序数组preorder进行切割 :前序左(begin/end) 前序右(begin/end)
6. 进行左右子树构建递归
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val = val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val = val;* this.left = left;* this.right = right;* }* }*/
class Solution {public TreeNode buildTree(int[] preorder, int[] inorder) {// 采用左闭右闭if(preorder.length == 0) return null;return helper(preorder, inorder, 0, preorder.length-1, 0, inorder.length-1);}public TreeNode helper(int[] preorder, int[] inorder, int preorderBegin, int preorderEnd, int inorderBegin, int inorderEnd){// 接受参数int[] preorder, int[] inorder, preorder的开始,preorder的结束,inorder的开始,inorder的结束// 1.如果数组大小为0,说明是空节点,return nullif(preorderBegin > preorderEnd){return null;}// 2.从前序的第一个得到根节点rootint midval = preorder[preorderBegin];TreeNode root = new TreeNode(midval);// 3. 根据midval 在中序数组inorder中 寻找切割点midindexint midindex;for(midindex = inorderBegin; midindex<=inorderEnd; midindex++){if(inorder[midindex] == midval){break;}}// 4.对中序数组inorder进行切割 :中序左(begin/end) 中序右(begin/end)int inorderLeftBegin = inorderBegin;int inorderLeftEnd = midindex-1;int inorderRightBegin =midindex+1;int inorderRightEnd = inorderEnd;// 5.根据分化结果,对前序数组preorder进行切割 :前序左(begin/end) 前序右(begin/end)int preorderLeftBegin = preorderBegin+1;int preorderLeftEnd = preorderLeftBegin + midindex-inorderBegin-1;int preorderRightBegin = preorderLeftEnd+1;int preorderRightEnd = preorderEnd;// 进行左右子树构建递归root.left = helper(preorder, inorder, preorderLeftBegin,preorderLeftEnd, inorderLeftBegin, inorderLeftEnd); //左root.right = helper(preorder, inorder, preorderRightBegin,preorderRightEnd, inorderRightBegin, inorderRightEnd); //右return root;}
}
相关文章:
★【递归】【构造二叉树】Leetcode 106.从中序与后序遍历序列构造二叉树
★【递归前序】【构造二叉树】Leetcode 106.从中序与后序遍历序列构造二叉树 105. 从前序与中序遍历序列构造二叉树 106.从中序与后序遍历序列构造二叉树:star:思路分析递归解法 105. 从前序与中序遍历序列构造二叉树递归解法 凡是构造二叉树>>>>>>>>&…...
linux检测和重启python脚本
#!/bin/bash# 检测Flask应用是否挂了 if ! pgrep -f "flask_app.py" >/dev/null; then# 重启Flask应用cd /path/to/your/flask/appnohup python3 flask_app.py >/dev/null 2>&1 & fi这是一个简单的bash脚本,用于检测Flask应用是否挂掉&a…...
HTML+CSS+JS:花瓣登录组件
效果演示 实现了一个具有动态花朵背景和简洁登录框的登录页面效果。 Code <section><img src"./img/background.jpeg" class"background"><div class"login"><h2>Sign In</h2><div class"inputBox"…...
Unity中URP下实现水体(水面反射)
文章目录 前言一、原理1、法一:使用立方体纹理 CubeMap,作为反射纹理使用2、法二:使用反射探针生成环境反射图,所谓反射的采样纹理 二、实现水面反射1、定义和申明CubeMap2、反射向量需要什么3、计算 N ⃗ \vec{N} N 4、计算 V ⃗…...
基于FastJson实现Json数据文件导入导出解析
哈喽,大家好,我是灰小猿,一个超会写bug的程序猿! 今天来记录一个在项目实战中比较实用的方法,主要是针对一些需要存在简单数据文件导入导出的场景,如:数据文件的简单备份、软件升版前后配置导入…...
JVM内存分配与垃圾收集流程
3.8 实战:内存分配与回收策略 3.8.1 对象优先在Eden分配 大多数情况下,对象在新生代Eden区中分配。当Eden区没有足够空间进行分配时,虚拟机将发起一次Minor GC。 3.8.2 大对象直接进入老年代 HotSpot虚拟机提供了-XX:Prete…...
【python】yaml转成json
姊妹篇:【python】json转成成yaml yaml数据: address:city: 北京市postalCode: 100000street: 北京路123号 age: 30 cart: - product:name: 笔记本电脑price: 1199.99quantity: 2 - product:name: 智能手机price: 599.99quantity: 1 children: - age: …...
css5定位
css 一.定位1.概念(定位定位模式边位移)2.静态位移static(不常用)3.相对定位relative(不脱标)(占位置)4.绝对定位absolute(脱标)(不占位置&#x…...
【解决】修改 UI界面渲染层级 的常见误区
开发平台:Unity 2021版本 问题描述 Unity 中管理 UI 上显示元素的前后层级关系大致为以下两种方式: 方式一:修改UI元素队列顺序与层级方式二:使用 Canvas 组件中的 Override Sort 属性配置 方式二 对应复杂的 UI 层级关系将常…...
蓝桥杯练习系统(算法训练)ALGO-995 24点
资源限制 内存限制:256.0MB C/C时间限制:1.0s Java时间限制:3.0s Python时间限制:5.0s 问题描述 24点游戏是一个非常有意思的游戏,很流行,玩法很简单:给你4张牌,每张牌上有数…...
汽车电子笔记:BootLoader升级过程疑难问题解决方式(Bootloader响应10 02 + 刷死拯救机制)
目录 1、概述 2、如何在BootLoader响应10 02 2.1、实现流程图 2.2、实现方式(代码思路) 3、刷死拯救机制(100%能救活,适配各类控制器...
高级RAG:揭秘PDF解析
原文地址:https://pub.towardsai.net/advanced-rag-02-unveiling-pdf-parsing-b84ae866344e 2024 年 2 月 3 日 附加内容:揭秘PDF解析:如何从科学pdf论文中提取公式 对于RAG,从文档中提取信息是一个不可避免的场景。确保从源头…...
Android之UI Automator框架源码分析(第九篇:UiDevice获取UiAutomation对象的过程分析)
前言 学习UiDevice对象,就需要看它的构造方法,构造方法中有UiDevice对象持有一些对象,每个对象都是我们分析程序的重点,毕竟UiDevice对象的功能,依赖这些组合的对象 备注:当前对象持有的对象,初…...
【C语言】指针初阶2.0版本
这篇博文我们来继续学习指针的其他内容 指针2.0 传值调用与传址调用传值调用传址调用 一维数组与指针理解数组名使用指针深入理解一维数组 二级指针指针数组二维数组与指针 传值调用与传址调用 在开始之前,我们需要先了解这个概念,后面才能够正常的学习…...
小红书关键词爬虫
标题 1 统计要收集的关键词,制作一个文件夹2 爬取每一页的内容3 爬取标题和内容4 如果内容可以被查看,爬取评论内容5 将结果进行汇总,并且每个帖子保存为一个json文件,具体内容6 总结 1 统计要收集的关键词,制作一个文…...
网络爬虫的危害,如何有效的防止非法利用
近年来,不法分子利用“爬虫”软件收集公民隐私数据案件屡见不鲜。2023年8月23日,北京市高级人民法院召开北京法院侵犯公民个人信息犯罪案件审判情况新闻通报会,通报侵犯公民个人隐私信息案件审判情况,并发布典型案例。在这些典型案…...
2024/2/29 备战蓝桥杯 6-1 二分
目录 查找 【深基13.例1】查找 - 洛谷 数对 A-B 数对 - 洛谷 砍树 [COCI 2011/2012 #5] EKO / 砍树 - 洛谷 参考连接:AcWing 789. 数的范围---二分法一次搞懂 - AcWing 1.程序中不要同时出现l mid, r mdi这两条语句。 2.如过程序中出现了l mid࿰…...
浅析ARMv8体系结构:原子操作
文章目录 概述LL/SC机制独占内存访问指令多字节独占内存访问指令 独占监视器经典自旋锁实现 LSE机制原子内存操作指令CAS指令交换指令 相关参考 概述 在编程中,当多个处理器或线程访问共享数据,并且至少有一个正在写入时,操作必须是原子的&a…...
综合练习(二)
目录 列出薪金比 SMITH 或 ALLEN 多的所有员工的编号、姓名、部门名称、领导姓名、部门人数,以及所在部门的平均工资、最高和最低工资 补充 spool Oracle从入门到总裁:https://blog.csdn.net/weixin_67859959/article/details/135209645 列出薪金比 SMITH 或 AL…...
sql-labs第46关(order by盲注脚本)
一、环境 网上有自己找 二、解释 order by 注入我们看他的true和false来进行注入出来 二、实操 让我们用sort 看看源码 最终我们的id是放到order by后面了 如果我们直接用列去排序 ?sortusername/password username: password: 可以看到顺序是不…...
浏览器访问 AWS ECS 上部署的 Docker 容器(监听 80 端口)
✅ 一、ECS 服务配置 Dockerfile 确保监听 80 端口 EXPOSE 80 CMD ["nginx", "-g", "daemon off;"]或 EXPOSE 80 CMD ["python3", "-m", "http.server", "80"]任务定义(Task Definition&…...
基于距离变化能量开销动态调整的WSN低功耗拓扑控制开销算法matlab仿真
目录 1.程序功能描述 2.测试软件版本以及运行结果展示 3.核心程序 4.算法仿真参数 5.算法理论概述 6.参考文献 7.完整程序 1.程序功能描述 通过动态调整节点通信的能量开销,平衡网络负载,延长WSN生命周期。具体通过建立基于距离的能量消耗模型&am…...
java 实现excel文件转pdf | 无水印 | 无限制
文章目录 目录 文章目录 前言 1.项目远程仓库配置 2.pom文件引入相关依赖 3.代码破解 二、Excel转PDF 1.代码实现 2.Aspose.License.xml 授权文件 总结 前言 java处理excel转pdf一直没找到什么好用的免费jar包工具,自己手写的难度,恐怕高级程序员花费一年的事件,也…...
ElasticSearch搜索引擎之倒排索引及其底层算法
文章目录 一、搜索引擎1、什么是搜索引擎?2、搜索引擎的分类3、常用的搜索引擎4、搜索引擎的特点二、倒排索引1、简介2、为什么倒排索引不用B+树1.创建时间长,文件大。2.其次,树深,IO次数可怕。3.索引可能会失效。4.精准度差。三. 倒排索引四、算法1、Term Index的算法2、 …...
AI病理诊断七剑下天山,医疗未来触手可及
一、病理诊断困局:刀尖上的医学艺术 1.1 金标准背后的隐痛 病理诊断被誉为"诊断的诊断",医生需通过显微镜观察组织切片,在细胞迷宫中捕捉癌变信号。某省病理质控报告显示,基层医院误诊率达12%-15%,专家会诊…...
C++.OpenGL (20/64)混合(Blending)
混合(Blending) 透明效果核心原理 #mermaid-svg-SWG0UzVfJms7Sm3e {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-SWG0UzVfJms7Sm3e .error-icon{fill:#552222;}#mermaid-svg-SWG0UzVfJms7Sm3e .error-text{fill…...
计算机基础知识解析:从应用到架构的全面拆解
目录 前言 1、 计算机的应用领域:无处不在的数字助手 2、 计算机的进化史:从算盘到量子计算 3、计算机的分类:不止 “台式机和笔记本” 4、计算机的组件:硬件与软件的协同 4.1 硬件:五大核心部件 4.2 软件&#…...
Golang——9、反射和文件操作
反射和文件操作 1、反射1.1、reflect.TypeOf()获取任意值的类型对象1.2、reflect.ValueOf()1.3、结构体反射 2、文件操作2.1、os.Open()打开文件2.2、方式一:使用Read()读取文件2.3、方式二:bufio读取文件2.4、方式三:os.ReadFile读取2.5、写…...
Cilium动手实验室: 精通之旅---13.Cilium LoadBalancer IPAM and L2 Service Announcement
Cilium动手实验室: 精通之旅---13.Cilium LoadBalancer IPAM and L2 Service Announcement 1. LAB环境2. L2公告策略2.1 部署Death Star2.2 访问服务2.3 部署L2公告策略2.4 服务宣告 3. 可视化 ARP 流量3.1 部署新服务3.2 准备可视化3.3 再次请求 4. 自动IPAM4.1 IPAM Pool4.2 …...
Java详解LeetCode 热题 100(26):LeetCode 142. 环形链表 II(Linked List Cycle II)详解
文章目录 1. 题目描述1.1 链表节点定义 2. 理解题目2.1 问题可视化2.2 核心挑战 3. 解法一:HashSet 标记访问法3.1 算法思路3.2 Java代码实现3.3 详细执行过程演示3.4 执行结果示例3.5 复杂度分析3.6 优缺点分析 4. 解法二:Floyd 快慢指针法(…...
