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

★【递归】【构造二叉树】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脚本&#xff0c;用于检测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、法一&#xff1a;使用立方体纹理 CubeMap&#xff0c;作为反射纹理使用2、法二&#xff1a;使用反射探针生成环境反射图&#xff0c;所谓反射的采样纹理 二、实现水面反射1、定义和申明CubeMap2、反射向量需要什么3、计算 N ⃗ \vec{N} N 4、计算 V ⃗…...

基于FastJson实现Json数据文件导入导出解析

哈喽&#xff0c;大家好&#xff0c;我是灰小猿&#xff0c;一个超会写bug的程序猿&#xff01; 今天来记录一个在项目实战中比较实用的方法&#xff0c;主要是针对一些需要存在简单数据文件导入导出的场景&#xff0c;如&#xff1a;数据文件的简单备份、软件升版前后配置导入…...

JVM内存分配与垃圾收集流程

3.8 实战&#xff1a;内存分配与回收策略 3.8.1 对象优先在Eden分配 大多数情况下&#xff0c;对象在新生代Eden区中分配。当Eden区没有足够空间进行分配时&#xff0c;虚拟机将发起一次Minor GC。 3.8.2 大对象直接进入老年代 HotSpot虚拟机提供了-XX&#xff1a;Prete…...

【python】yaml转成json

姊妹篇&#xff1a;【python】json转成成yaml yaml数据&#xff1a; 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.概念&#xff08;定位定位模式边位移&#xff09;2.静态位移static&#xff08;不常用&#xff09;3.相对定位relative&#xff08;不脱标&#xff09;&#xff08;占位置&#xff09;4.绝对定位absolute&#xff08;脱标&#xff09;&#xff08;不占位置&#x…...

【解决】修改 UI界面渲染层级 的常见误区

开发平台&#xff1a;Unity 2021版本   问题描述 Unity 中管理 UI 上显示元素的前后层级关系大致为以下两种方式&#xff1a; 方式一&#xff1a;修改UI元素队列顺序与层级方式二&#xff1a;使用 Canvas 组件中的 Override Sort 属性配置 方式二 对应复杂的 UI 层级关系将常…...

蓝桥杯练习系统(算法训练)ALGO-995 24点

资源限制 内存限制&#xff1a;256.0MB C/C时间限制&#xff1a;1.0s Java时间限制&#xff1a;3.0s Python时间限制&#xff1a;5.0s 问题描述 24点游戏是一个非常有意思的游戏&#xff0c;很流行&#xff0c;玩法很简单&#xff1a;给你4张牌&#xff0c;每张牌上有数…...

汽车电子笔记:BootLoader升级过程疑难问题解决方式(Bootloader响应10 02 + 刷死拯救机制)

目录 1、概述 2、如何在BootLoader响应10 02 2.1、实现流程图 2.2、实现方式(代码思路) 3、刷死拯救机制(100%能救活,适配各类控制器...

高级RAG:揭秘PDF解析

原文地址&#xff1a;https://pub.towardsai.net/advanced-rag-02-unveiling-pdf-parsing-b84ae866344e 2024 年 2 月 3 日 附加内容&#xff1a;揭秘PDF解析&#xff1a;如何从科学pdf论文中提取公式 对于RAG&#xff0c;从文档中提取信息是一个不可避免的场景。确保从源头…...

Android之UI Automator框架源码分析(第九篇:UiDevice获取UiAutomation对象的过程分析)

前言 学习UiDevice对象&#xff0c;就需要看它的构造方法&#xff0c;构造方法中有UiDevice对象持有一些对象&#xff0c;每个对象都是我们分析程序的重点&#xff0c;毕竟UiDevice对象的功能&#xff0c;依赖这些组合的对象 备注&#xff1a;当前对象持有的对象&#xff0c;初…...

【C语言】指针初阶2.0版本

这篇博文我们来继续学习指针的其他内容 指针2.0 传值调用与传址调用传值调用传址调用 一维数组与指针理解数组名使用指针深入理解一维数组 二级指针指针数组二维数组与指针 传值调用与传址调用 在开始之前&#xff0c;我们需要先了解这个概念&#xff0c;后面才能够正常的学习…...

小红书关键词爬虫

标题 1 统计要收集的关键词&#xff0c;制作一个文件夹2 爬取每一页的内容3 爬取标题和内容4 如果内容可以被查看&#xff0c;爬取评论内容5 将结果进行汇总&#xff0c;并且每个帖子保存为一个json文件&#xff0c;具体内容6 总结 1 统计要收集的关键词&#xff0c;制作一个文…...

网络爬虫的危害,如何有效的防止非法利用

近年来&#xff0c;不法分子利用“爬虫”软件收集公民隐私数据案件屡见不鲜。2023年8月23日&#xff0c;北京市高级人民法院召开北京法院侵犯公民个人信息犯罪案件审判情况新闻通报会&#xff0c;通报侵犯公民个人隐私信息案件审判情况&#xff0c;并发布典型案例。在这些典型案…...

2024/2/29 备战蓝桥杯 6-1 二分

目录 查找 【深基13.例1】查找 - 洛谷 数对 A-B 数对 - 洛谷 砍树 [COCI 2011/2012 #5] EKO / 砍树 - 洛谷 参考连接&#xff1a;AcWing 789. 数的范围---二分法一次搞懂 - AcWing 1.程序中不要同时出现l mid, r mdi这两条语句。 2.如过程序中出现了l mid&#xff0…...

浅析ARMv8体系结构:原子操作

文章目录 概述LL/SC机制独占内存访问指令多字节独占内存访问指令 独占监视器经典自旋锁实现 LSE机制原子内存操作指令CAS指令交换指令 相关参考 概述 在编程中&#xff0c;当多个处理器或线程访问共享数据&#xff0c;并且至少有一个正在写入时&#xff0c;操作必须是原子的&a…...

综合练习(二)

目录 列出薪金比 SMITH 或 ALLEN 多的所有员工的编号、姓名、部门名称、领导姓名、部门人数&#xff0c;以及所在部门的平均工资、最高和最低工资 补充 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&#xff1a; password&#xff1a; 可以看到顺序是不…...

后进先出(LIFO)详解

LIFO 是 Last In, First Out 的缩写&#xff0c;中文译为后进先出。这是一种数据结构的工作原则&#xff0c;类似于一摞盘子或一叠书本&#xff1a; 最后放进去的元素最先出来 -想象往筒状容器里放盘子&#xff1a; &#xff08;1&#xff09;你放进的最后一个盘子&#xff08…...

(LeetCode 每日一题) 3442. 奇偶频次间的最大差值 I (哈希、字符串)

题目&#xff1a;3442. 奇偶频次间的最大差值 I 思路 &#xff1a;哈希&#xff0c;时间复杂度0(n)。 用哈希表来记录每个字符串中字符的分布情况&#xff0c;哈希表这里用数组即可实现。 C版本&#xff1a; class Solution { public:int maxDifference(string s) {int a[26]…...

微软PowerBI考试 PL300-选择 Power BI 模型框架【附练习数据】

微软PowerBI考试 PL300-选择 Power BI 模型框架 20 多年来&#xff0c;Microsoft 持续对企业商业智能 (BI) 进行大量投资。 Azure Analysis Services (AAS) 和 SQL Server Analysis Services (SSAS) 基于无数企业使用的成熟的 BI 数据建模技术。 同样的技术也是 Power BI 数据…...

#Uniapp篇:chrome调试unapp适配

chrome调试设备----使用Android模拟机开发调试移动端页面 Chrome://inspect/#devices MuMu模拟器Edge浏览器&#xff1a;Android原生APP嵌入的H5页面元素定位 chrome://inspect/#devices uniapp单位适配 根路径下 postcss.config.js 需要装这些插件 “postcss”: “^8.5.…...

在QWebEngineView上实现鼠标、触摸等事件捕获的解决方案

这个问题我看其他博主也写了&#xff0c;要么要会员、要么写的乱七八糟。这里我整理一下&#xff0c;把问题说清楚并且给出代码&#xff0c;拿去用就行&#xff0c;照着葫芦画瓢。 问题 在继承QWebEngineView后&#xff0c;重写mousePressEvent或event函数无法捕获鼠标按下事…...

GitHub 趋势日报 (2025年06月06日)

&#x1f4ca; 由 TrendForge 系统生成 | &#x1f310; https://trendforge.devlive.org/ &#x1f310; 本日报中的项目描述已自动翻译为中文 &#x1f4c8; 今日获星趋势图 今日获星趋势图 590 cognee 551 onlook 399 project-based-learning 348 build-your-own-x 320 ne…...

快刀集(1): 一刀斩断视频片头广告

一刀流&#xff1a;用一个简单脚本&#xff0c;秒杀视频片头广告&#xff0c;还你清爽观影体验。 1. 引子 作为一个爱生活、爱学习、爱收藏高清资源的老码农&#xff0c;平时写代码之余看看电影、补补片&#xff0c;是再正常不过的事。 电影嘛&#xff0c;要沉浸&#xff0c;…...

逻辑回归暴力训练预测金融欺诈

简述 「使用逻辑回归暴力预测金融欺诈&#xff0c;并不断增加特征维度持续测试」的做法&#xff0c;体现了一种逐步建模与迭代验证的实验思路&#xff0c;在金融欺诈检测中非常有价值&#xff0c;本文作为一篇回顾性记录了早年间公司给某行做反欺诈预测用到的技术和思路。百度…...

Axure Rp 11 安装、汉化、授权

Axure Rp 11 安装、汉化、授权 1、前言2、汉化2.1、汉化文件下载2.2、windows汉化流程2.3、 macOs汉化流程 3、授权 1、前言 Axure Rp 11官方下载链接&#xff1a;https://www.axure.com/downloadthanks 2、汉化 2.1、汉化文件下载 链接: https://pan.baidu.com/s/18Clf…...

21-Oracle 23 ai-Automatic SQL Plan Management(SPM)

小伙伴们&#xff0c;有没有迁移数据库完毕后或是突然某一天在同一个实例上同样的SQL&#xff0c; 性能不一样了、业务反馈卡顿、业务超时等各种匪夷所思的现状。 于是SPM定位开始&#xff0c;OCM考试中SPM必考。 其他的AWR、ASH、SQLHC、SQLT、SQL profile等换作下一个话题…...