LeetCode105.从前序和中序遍历序列构造二叉树


这道题看完题想了几分钟就想到大概的思路了,但是在写的时候有很多细节没注意出了很多问题,然后写了1个多小时,其实这道题挺简单的。
首先,最基本的知识,先序遍历是根左右,中序遍历是左根右,那么我们一眼可以知道:根节点是先序遍历的第一个节点,然后又可以在中序遍历中找到这个根节点(树中每个val都不相等),中序遍历中根节点的左变是左子树,根节点的右遍是右子树。
那么这个题目应该怎么解呢?首先,对于树的题目要么递归要么用队列或栈,我选择用递归。根据上面发现的几个点,我想到了递归函数:
public TreeNode dfs(int[] preorder, int[] inorder)
通过这两个遍历序列我们可以创建出根节点,然后我们在从preorder和inorder中找出来左子树的leftPreorder和leftInorder以及右子树的rightPreorder和rightInorder,然后利用递归
root.left=dfs(leftPreorder, leftInorder);
root.right = dfs(rightPreorder, rightInorder);
大体上的思路就是这样,那么我们如何找出左右子树的前序和中序的遍历序列呢?
首先中序遍历是非常简单的,中序遍历是左根右的顺序,它对于每颗树都是根左右的顺序,所以‘左’就是左子树的中序遍历结果,所以我们在inorder中根节点左边就是leftInorder,根节点右边就是rightInorder。
前序遍历也不难,前序遍历是根左右,preorder第0个数是根节点,后面是左和右,而我们在中序遍历中已经知道了左子树的长度leftLength和右子树的长度rightLength,所有从第1个数往后数leftLength就是左子树的前序遍历leftPreorder,剩下的就是右子树的前序遍历rightPreorder。
然后需要注意的就是,递归的结束,如果左子树的长度小于0就不用递归的创建左子树了,右子树同理,最后返回root。以下是我的代码:
class Solution {public TreeNode buildTree(int[] preorder, int[] inorder) {if(preorder.length == 0){return null;}else{return dfs(preorder, inorder);}}public TreeNode dfs(int[] preorder, int[] inorder){TreeNode root = new TreeNode(preorder[0]);int leftInorderIndex = 0;int rightInorderIndex = 0;int leftPreorderIndex = 0;int rightPreorderIndex = 0;//在中序遍历中找到根节点for(int i=0;i<inorder.length;i++){if(inorder[i] == root.val){leftInorderIndex = i-1;rightInorderIndex = i+1;break;}}//找到左子树长度和右子树长度int leftLength = leftInorderIndex+1;int rightLength = inorder.length - rightInorderIndex;if(leftLength > 0){//创建leftInorderint[] leftInorder = new int[leftLength];for(int i=0;i<leftInorder.length;i++){leftInorder[i] = inorder[i];}//创建leftPreorderint[] leftPreorder = new int[leftLength];int index =1;for(int i=0;i<leftPreorder.length;i++){leftPreorder[i] = preorder[index];index++;}//递归出根节点的左子树root.left = dfs(leftPreorder, leftInorder);}if(rightLength > 0){//创建出rightInorderrightPreorderIndex = leftLength+1;int[] rightInorder = new int[rightLength];int index0= rightInorderIndex;for(int i=0;i<rightInorder.length;i++){rightInorder[i] = inorder[index0];index0++;}//创建出rightPreorderint[] rightPreorder = new int[rightLength];int index1 = rightPreorderIndex;for(int i=0;i<rightPreorder.length;i++){rightPreorder[i] = preorder[index1];index1++;}//递归出根节点的右子树root.right = dfs(rightPreorder, rightInorder);}return root;}
}
看看官方题解做法:
题解的方法一用的也是递归,但是他用了一个HashMap来快速定位根节点,还有就是他没有去创建左右子树的前中遍历序列数组,他直接传前序,中序遍历在inorder中的起始下标和终止下标,因为他们在数组中是连续的,这样全局只需要用这个最大的inorder和preorder就可以,不用花费时间和空间去创建数组,以下是题解方法一代码:
class Solution {private Map<Integer, Integer> indexMap;public TreeNode myBuildTree(int[] preorder, int[] inorder, int preorder_left, int preorder_right, int inorder_left, int inorder_right) {if (preorder_left > preorder_right) {return null;}// 前序遍历中的第一个节点就是根节点int preorder_root = preorder_left;// 在中序遍历中定位根节点int inorder_root = indexMap.get(preorder[preorder_root]);// 先把根节点建立出来TreeNode root = new TreeNode(preorder[preorder_root]);// 得到左子树中的节点数目int size_left_subtree = inorder_root - inorder_left;// 递归地构造左子树,并连接到根节点// 先序遍历中「从 左边界+1 开始的 size_left_subtree」个元素就对应了中序遍历中「从 左边界 开始到 根节点定位-1」的元素root.left = myBuildTree(preorder, inorder, preorder_left + 1, preorder_left + size_left_subtree, inorder_left, inorder_root - 1);// 递归地构造右子树,并连接到根节点// 先序遍历中「从 左边界+1+左子树节点数目 开始到 右边界」的元素就对应了中序遍历中「从 根节点定位+1 到 右边界」的元素root.right = myBuildTree(preorder, inorder, preorder_left + size_left_subtree + 1, preorder_right, inorder_root + 1, inorder_right);return root;}public TreeNode buildTree(int[] preorder, int[] inorder) {int n = preorder.length;// 构造哈希映射,帮助我们快速定位根节点indexMap = new HashMap<Integer, Integer>();for (int i = 0; i < n; i++) {indexMap.put(inorder[i], i);}return myBuildTree(preorder, inorder, 0, n - 1, 0, n - 1);}
}
题解的第二种方法是迭代,
class Solution {public TreeNode buildTree(int[] preorder, int[] inorder) {if (preorder == null || preorder.length == 0) {return null;}TreeNode root = new TreeNode(preorder[0]);Deque<TreeNode> stack = new LinkedList<TreeNode>();stack.push(root);int inorderIndex = 0;for (int i = 1; i < preorder.length; i++) {int preorderVal = preorder[i];TreeNode node = stack.peek();if (node.val != inorder[inorderIndex]) {node.left = new TreeNode(preorderVal);stack.push(node.left);} else {while (!stack.isEmpty() && stack.peek().val == inorder[inorderIndex]) {node = stack.pop();inorderIndex++;}node.right = new TreeNode(preorderVal);stack.push(node.right);}}return root;}
}相关文章:
LeetCode105.从前序和中序遍历序列构造二叉树
这道题看完题想了几分钟就想到大概的思路了,但是在写的时候有很多细节没注意出了很多问题,然后写了1个多小时,其实这道题挺简单的。 首先,最基本的知识,先序遍历是根左右,中序遍历是左根右,那么…...
flutter-一个可以输入的数字增减器
效果 参考文章 代码 在参考文章上边,主要是改了一下样式,逻辑也比较清楚,对左右两边添加增减方法。 我在此基础上加了_numcontroller 输入框的监听。 加了数字输入框的控制 keyboardType: TextInputType.number, //设置键盘为数字 inputF…...
抑郁症中西医治疗对比?
抑郁症是一种常见的心理障碍,治疗方法包括中医和西医两种。下面就抑郁症中西医治疗进行对比: 治疗方法:中医治疗抑郁症强调整体观念和辨证论治,通过调理身体各部分的功能,达到治疗抑郁症的目的。中医治疗抑郁症多采用天…...
012 OpenCV sobel边缘检测
目录 一、环境 二、soble原理介绍 三、源码实验 一、环境 本文使用环境为: Windows10Python 3.9.17opencv-python 4.8.0.74 二、soble原理介绍 Sobel边缘检测是一种广泛应用于图像处理领域的边缘检测算法,它通过计算图像灰度函数在水平方向和垂直…...
【开源视频联动物联网平台】libmodbus 写一个modbus tcp客户端
libmodbus 是一个用于 Modbus 通信协议的 C 语言库,可以用来创建 Modbus TCP 客户端。以下是一个简单的示例代码,演示如何使用 libmodbus 创建一个 Modbus TCP 客户端。 首先,确保你已经安装了 libmodbus 库。你可以从 libmodbus 的官方网站…...
安装以及使用 stylepro_artistic 所遇问题解决
根据https://github.com/PaddlePaddle/PaddleHub/blob/develop/docs/docs_ch/get_start/windows_quickstart.md 安装 hub install stylepro_artistic1.0.1 出现ImportError: cannot import name ‘Constant’ from ‘paddle.fluid.initializer’,提示在File: "…...
【Rust】所有权的认识
所有权 所有权的认识移动,克隆,拷贝所有权与函数返回值与作用域 引用与借用可变引用悬垂引用(Dangling References) Slice类型 所有权的认识 所有程序都必须管理其运行时使用计算机内存的方式。一些语言中具有垃圾回收机制&#…...
中间件安全:Weblogic 漏洞.(使用工具可以利用多种类型漏洞)
中间件安全:Weblogic 漏洞.(使用工具可以利用多种类型漏洞) WebLogic 是美国 Oracle 公司出品的一个 application server,确切的说是一个基于 JAVA EE 架构的中间件,WebLogic 是用于开发、集成、部署和管理大型分布式…...
matlab操作方法(一)——向量及其操作
1.向量及其操作 matlab是英文Matrix Laboratory(矩阵实验室)的简称,是基于矩阵运算的操作环境。matlab中的所有数据都是以矩阵或多维数组的形式存储的。向量和标量是矩阵的两种特殊形式 向量是指单行或者单列的矩阵,它是构成矩阵…...
MicroPython标准库
MicroPython标准库 arraybinascii(二进制/ASCII转换)builtins – 内置函数和异常cmath – 复数的数学函数collections – 集合和容器类型errno – 系统错误代码gc – 控制垃圾收集器hashlib – 散列算法heapq – 堆队列算法io – 输入/输出流json – JSON 编码和解码math – 数…...
2023年产业数据价值化峰会暨数栖大会-核心PPT资料下载
一、峰会简介 本次大会由主论坛和3场分论坛组成,嘉宾阵容强大,内容丰富多彩。来自政企学界的百名专家从产学研用多种维度对企业数据管理、产业数据资源化建设等视角展开。大会围绕“产业数据价值化”为主题,秉持“让数据用起来”的使命&…...
深入理解 Vue 组件:构建优雅的前端应用
🍂引言: Vue.js 是一款流行的 JavaScript 框架,以其简单易用和高度灵活的特性而受到了广泛的欢迎。其中的一个重要概念就是组件,它使我们能够将用户界面划分为可重用的、独立的部分。本文将深入探讨 Vue 组件的概念、使用和最佳实…...
基于SpringBoot+Vue的前后端分离的房屋租赁系统2
✌全网粉丝20W,csdn特邀作者、博客专家、CSDN新星计划导师、java领域优质创作者,博客之星、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和毕业项目实战✌ 🍅文末获取项目下载方式🍅 一、项目背景介绍: 开发过程中࿰…...
PHPExcel 导出Excel报错:PHPExcel_IOFactory::load()
背景 近期在做 excel文件数据导出时,遇到如下报错: iconv(): Detected an illegal character in input string场景:计划任务后台,分步导出 大数据 excel文件发现在加载文件时,会有报错 报错信息 如下: {&q…...
Jmeter-分布式压测(远程启动服务器,windows)
1 前提条件 JDK已部署,版本一致Jmeter已部署,版本一致多台服务器连接的同一网络(例如:同一wifi)防火墙处于关闭状态(或者对应默认端口处于开放状态)虚拟网络适配器都处于关闭状态查找到每一台服务器的IP 2 主服务器配…...
【C++】string类模拟实现过程中值得注意的点
👀樊梓慕:个人主页 🎥个人专栏:《C语言》《数据结构》《蓝桥杯试题》《LeetCode刷题笔记》《实训项目》《C》《Linux》 🌝每一个不曾起舞的日子,都是对生命的辜负 目录 前言 1.有关const的使用 &#x…...
大数据湖项目建设方案:文档全文101页,附下载
关键词:大数据解决方案,数据湖解决方案,数据治理解决方案,数据中台解决方案 一、大数据湖建设思路 1、明确目标和定位:明确大数据湖的目标和定位是整个项目的基础,这可以帮助我们确定项目的内容、规模、所…...
通付盾Web3专题 | SharkTeam:起底朝鲜APT组织Lazarus Group,攻击手法及洗钱模式
国家级APT(Advanced Persistent Threat,高级持续性威胁)组织是有国家背景支持的顶尖黑客团伙,专门针对特定目标进行长期的持续性网络攻击。朝鲜APT组织Lazarus Group就是非常活跃的一个APT团伙,其攻击目的主要以窃取资…...
<蓝桥杯软件赛>零基础备赛20周--第8周第1讲--十大排序
报名明年4月蓝桥杯软件赛的同学们,如果你是大一零基础,目前懵懂中,不知该怎么办,可以看看本博客系列:备赛20周合集 20周的完整安排请点击:20周计划 每周发1个博客,共20周(读者可以按…...
数据增强让模型更健壮
在做一些图像分类训练任务时,我们经常会遇到一个很尴尬的情况,那就是: 明明训练数据集中有很多可爱猫咪的照片,但是当我们给训练好的模型输入一张戴着头盔的猫咪进行测试时,模型就不认识了,或者说识别精度很低。 很明显,模型的泛化能力太差,难道戴着头盔的猫咪就不是猫…...
深入剖析AI大模型:大模型时代的 Prompt 工程全解析
今天聊的内容,我认为是AI开发里面非常重要的内容。它在AI开发里无处不在,当你对 AI 助手说 "用李白的风格写一首关于人工智能的诗",或者让翻译模型 "将这段合同翻译成商务日语" 时,输入的这句话就是 Prompt。…...
Spring Boot 实现流式响应(兼容 2.7.x)
在实际开发中,我们可能会遇到一些流式数据处理的场景,比如接收来自上游接口的 Server-Sent Events(SSE) 或 流式 JSON 内容,并将其原样中转给前端页面或客户端。这种情况下,传统的 RestTemplate 缓存机制会…...
ESP32读取DHT11温湿度数据
芯片:ESP32 环境:Arduino 一、安装DHT11传感器库 红框的库,别安装错了 二、代码 注意,DATA口要连接在D15上 #include "DHT.h" // 包含DHT库#define DHTPIN 15 // 定义DHT11数据引脚连接到ESP32的GPIO15 #define D…...
uniapp中使用aixos 报错
问题: 在uniapp中使用aixos,运行后报如下错误: AxiosError: There is no suitable adapter to dispatch the request since : - adapter xhr is not supported by the environment - adapter http is not available in the build 解决方案&…...
安宝特案例丨Vuzix AR智能眼镜集成专业软件,助力卢森堡医院药房转型,赢得辉瑞创新奖
在Vuzix M400 AR智能眼镜的助力下,卢森堡罗伯特舒曼医院(the Robert Schuman Hospitals, HRS)凭借在无菌制剂生产流程中引入增强现实技术(AR)创新项目,荣获了2024年6月7日由卢森堡医院药剂师协会࿰…...
排序算法总结(C++)
目录 一、稳定性二、排序算法选择、冒泡、插入排序归并排序随机快速排序堆排序基数排序计数排序 三、总结 一、稳定性 排序算法的稳定性是指:同样大小的样本 **(同样大小的数据)**在排序之后不会改变原始的相对次序。 稳定性对基础类型对象…...
Linux 中如何提取压缩文件 ?
Linux 是一种流行的开源操作系统,它提供了许多工具来管理、压缩和解压缩文件。压缩文件有助于节省存储空间,使数据传输更快。本指南将向您展示如何在 Linux 中提取不同类型的压缩文件。 1. Unpacking ZIP Files ZIP 文件是非常常见的,要在 …...
MySQL 索引底层结构揭秘:B-Tree 与 B+Tree 的区别与应用
文章目录 一、背景知识:什么是 B-Tree 和 BTree? B-Tree(平衡多路查找树) BTree(B-Tree 的变种) 二、结构对比:一张图看懂 三、为什么 MySQL InnoDB 选择 BTree? 1. 范围查询更快 2…...
DAY 26 函数专题1
函数定义与参数知识点回顾:1. 函数的定义2. 变量作用域:局部变量和全局变量3. 函数的参数类型:位置参数、默认参数、不定参数4. 传递参数的手段:关键词参数5 题目1:计算圆的面积 任务: 编写一…...
【大模型】RankRAG:基于大模型的上下文排序与检索增强生成的统一框架
文章目录 A 论文出处B 背景B.1 背景介绍B.2 问题提出B.3 创新点 C 模型结构C.1 指令微调阶段C.2 排名与生成的总和指令微调阶段C.3 RankRAG推理:检索-重排-生成 D 实验设计E 个人总结 A 论文出处 论文题目:RankRAG:Unifying Context Ranking…...
