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

leetcode--从中序与后序遍历序列构造二叉树

leeocode地址:从中序与后序遍历序列构造二叉树
给定两个整数数组 inorder 和 postorder ,其中 inorder 是二叉树的中序遍历, postorder 是同一棵树的后序遍历,请你构造并返回这颗 二叉树 。

示例 1:
在这里插入图片描述

输入:inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
输出:[3,9,20,null,null,15,7]
示例 2:

输入:inorder = [-1], postorder = [-1]
输出:[-1]

提示:
1 <= inorder.length <= 3000
postorder.length == inorder.length
-3000 <= inorder[i], postorder[i] <= 3000
inorder 和 postorder 都由 不同 的值组成
postorder 中每一个值都在 inorder 中
inorder 保证是树的中序遍历
postorder 保证是树的后序遍历

实现思路

中序遍历(Inorder):左子树 -> 根节点 -> 右子树
后序遍历(Postorder):左子树 -> 右子树 -> 根节点
通过给定的中序遍历和后序遍历数组,我们可以确定二叉树的根节点以及左右子树的范围。具体步骤如下:
步骤1:后序遍历的最后一个元素是根节点的值。
步骤2:在中序遍历中找到根节点的位置,其左侧为左子树的中序遍历,右侧为右子树的中序遍历。
步骤3:根据步骤2中左右子树的大小,可以在后序遍历中确定左子树和右子树的后序遍历。
递归地应用以上步骤,即可构造整棵二叉树。

代码实现

# Definition for a binary tree node.
class TreeNode:def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = rightdef buildTree(inorder, postorder):if not inorder or not postorder:return Noneroot_val = postorder.pop()root = TreeNode(root_val)idx = inorder.index(root_val)root.right = buildTree(inorder[idx + 1:], postorder)root.left = buildTree(inorder[:idx], postorder)return rootdef inorderTraversal(root):if not root:return []return inorderTraversal(root.left) + [root.val] + inorderTraversal(root.right)# Example
inorder = [9, 3, 15, 20, 7]
postorder = [9, 15, 7, 20, 3]root = buildTree(inorder, postorder)# Verify the constructed tree by printing its inorder traversal
print("Inorder traversal of constructed tree:", inorderTraversal(root))

go实现

package mainimport "fmt"type TreeNode struct {Val   intLeft  *TreeNodeRight *TreeNode
}func buildTree(inorder []int, postorder []int) *TreeNode {if len(inorder) == 0 || len(postorder) == 0 {return nil}rootVal := postorder[len(postorder)-1]root := &TreeNode{Val: rootVal}idx := indexOf(inorder, rootVal)root.Left = buildTree(inorder[:idx], postorder[:idx])root.Right = buildTree(inorder[idx+1:], postorder[idx:len(postorder)-1])return root
}func indexOf(arr []int, val int) int {for i := range arr {if arr[i] == val {return i}}return -1
}func inorderTraversal(root *TreeNode) []int {var result []intvar inorder func(node *TreeNode)inorder = func(node *TreeNode) {if node == nil {return}inorder(node.Left)result = append(result, node.Val)inorder(node.Right)}inorder(root)return result
}func main() {// Exampleinorder := []int{9, 3, 15, 20, 7}postorder := []int{9, 15, 7, 20, 3}root := buildTree(inorder, postorder)// Verify the constructed tree by printing its inorder traversalfmt.Println("Inorder traversal of constructed tree:", inorderTraversal(root))
}

kotlin实现

class TreeNode(var `val`: Int) {var left: TreeNode? = nullvar right: TreeNode? = null
}fun buildTree(inorder: IntArray, postorder: IntArray): TreeNode? {if (inorder.isEmpty() || postorder.isEmpty()) {return null}val rootVal = postorder.last()val root = TreeNode(rootVal)val idx = inorder.indexOf(rootVal)root.left = buildTree(inorder.sliceArray(0 until idx), postorder.sliceArray(0 until idx))root.right = buildTree(inorder.sliceArray(idx + 1 until inorder.size), postorder.sliceArray(idx until postorder.size - 1))return root
}fun inorderTraversal(root: TreeNode?): List<Int> {val result = mutableListOf<Int>()fun inorder(node: TreeNode?) {if (node == null) returninorder(node.left)result.add(node.`val`)inorder(node.right)}inorder(root)return result
}fun main() {// Exampleval inorder = intArrayOf(9, 3, 15, 20, 7)val postorder = intArrayOf(9, 15, 7, 20, 3)val root = buildTree(inorder, postorder)// Verify the constructed tree by printing its inorder traversalprintln("Inorder traversal of constructed tree: ${inorderTraversal(root)}")
}

相关文章:

leetcode--从中序与后序遍历序列构造二叉树

leeocode地址&#xff1a;从中序与后序遍历序列构造二叉树 给定两个整数数组 inorder 和 postorder &#xff0c;其中 inorder 是二叉树的中序遍历&#xff0c; postorder 是同一棵树的后序遍历&#xff0c;请你构造并返回这颗 二叉树 。 示例 1: 输入&#xff1a;inorder …...

西瓜杯CTF(1)

#下班之前写了两个题&#xff0c;后面继续发 Codeinject <?php#Author: h1xaerror_reporting(0); show_source(__FILE__);eval("var_dump((Object)$_POST[1]);"); payload 闭合后面的括号来拼接 POST / HTTP/1.1 Host: 1dc86f1a-cccc-4298-955d-e9179f026d54…...

Kafka 典型问题与排查以及相关优化

Kafka 是一个高吞吐量的分布式消息系统&#xff0c;但在实际应用中&#xff0c;用户经常会遇到一些性能问题和消息堆积的问题。本文将介绍 Kafka 中一些典型问题的原因和排查方法&#xff0c;帮助用户解决问题并优化 Kafka 集群的性能。 一、Topic 消息发送慢&#xff0c;并发性…...

C# 策略模式(Strategy Pattern)

策略模式定义了一系列的算法&#xff0c;并将每一个算法封装起来&#xff0c;使它们可以相互替换。策略模式让算法的变化独立于使用算法的客户。 // 策略接口 public interface IStrategy { void Execute(); } // 具体策略A public class ConcreteStrategyA : IStra…...

【初阶数据结构】1.算法复杂度

文章目录 1.数据结构前言1.1 数据结构1.2 算法1.3 如何学好数据结构和算法 2.算法效率2.1 复杂度的概念2.2 复杂度的重要性 3.时间复杂度3.1 大O的渐进表示法3.2 时间复杂度计算示例3.2.1 示例13.2.2 示例23.2.3 示例33.2.4 示例43.2.5 示例53.2.6 示例63.2.7 示例7 4.空间复杂…...

(图文详解)小程序AppID申请以及在Hbuilderx中运行

今天小编给大家带来了如何去申请APPID&#xff0c;如果你是小程序的开发者&#xff0c;就必须要这个id。 申请步骤 到小程序注册页面&#xff0c;注册一个小程序账号 微信公众平台 填完信息后提交注册 会在邮箱收到 链接激活账号 确认。邮箱打开链接后&#xff0c;会输入实…...

科技创新引领水利行业升级:深入分析智慧水利解决方案的核心价值,展望其在未来水资源管理中的重要地位与作用

目录 引言 一、智慧水利的概念与内涵 二、智慧水利解决方案的核心价值 1. 精准监测与预警 2. 优化资源配置 3. 智能运维管理 4. 公众参与与决策支持 三、智慧水利在未来水资源管理中的重要地位与作用 1. 推动水利行业转型升级 2. 保障国家水安全 3. 促进生态文明建设…...

ExcelVBA运用Excel的【条件格式】(三)

ExcelVBA运用Excel的【条件格式】&#xff08;三&#xff09;前面知识点回顾1. 访问 FormatConditions 集合 Range.FormatConditions2. 添加条件格式 FormatConditions.Add 方法语法表达式。添加 (类型、 运算符、 Expression1、 Expression2)其中 TextOperator:***&am…...

coco数据集格式计算mAP的python脚本

目录 背景说明COCOeval 计算mAPtxt文件转换为coco json 格式自定义数据集标注 背景说明 在完成YOLOv5模型移植&#xff0c;运行在板端后&#xff0c;通常需要衡量板端运行的mAP。 一般需要两个步骤 步骤一&#xff1a;在板端批量运行得到目标检测结果&#xff0c;可保存为yol…...

Linux学习——Linux中无法使用ifconfg命令

Linux学习——Linux中无法使用ifconfg命令&#xff1f; &#x1f49d;&#x1f49d;&#x1f49d;欢迎来到我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅…...

二分查找3

1. 有序数组中的单一元素&#xff08;540&#xff09; 题目描述&#xff1a; 算法原理&#xff1a; 二分查找解题关键就在于去找到数组的二段性&#xff0c;这里数组的二段性是从单个数字a开始出现然后分隔出来的&#xff0c;如果mid落入左半部分那么当mid为偶数时nums[mid1]…...

从零开始学习嵌入式----C语言框架梳理与后期规划

目录 一、环境搭建. 二、见解 三、C语言框架梳理 四、嵌入式学习规划流程图&#xff08;学习顺序可能有变&#xff09; 一、环境搭建. C语言是一门编程语言&#xff0c;在学习的时候要准备好环境。我个人比较喜欢用VS,具体怎么安装请百度。学习C语言的时候&#xff0c;切忌…...

ESP32 步进电机精准控制:打造高精度 DIY 写字机器人,实现流畅书写体验

摘要: 想让你的 ESP32 不再仅仅是控制灯光的工具吗&#xff1f; 本文将带你使用 ESP32 开发板、步进电机和简单的机械结构打造一个能够自动写字的机器人。我们将深入浅出地讲解硬件连接、软件代码以及控制逻辑&#xff0c;并提供完整的项目代码和电路图&#xff0c;即使是 Ardu…...

传知代码-图神经网络长对话理解(论文复现)

代码以及视频讲解 本文所涉及所有资源均在传知代码平台可获取 概述 情感识别是人类对话理解的关键任务。随着多模态数据的概念&#xff0c;如语言、声音和面部表情&#xff0c;任务变得更加具有挑战性。作为典型解决方案&#xff0c;利用全局和局部上下文信息来预测对话中每…...

部署前端项目

常见部署方式有&#xff1a;静态托管服务、服务器部署 1. 静态托管服务 使用平台部署代码&#xff0c;比如 GitHub。 | 创建一个仓库&#xff0c;仓库名一般是 yourGithubName.github.io。 | 将打包后的静态文件文件上传到仓库。 | 在“Settings”&#xff08;选项&#xff0…...

使用POI实现Excel文件的读取(超详细)

目录 一 导入poi相关的maven坐标 二 实现创建并且写入文件 2.1实现步骤 2.2实现代码 2.3效果展示 ​编辑 2.4注意 三 实现从Excel文件中读取数据 3.1实现步骤 3.2实现代码 3.3结果展示 一 导入poi相关的maven坐标 <!-- Apache poi --><dependency><gro…...

Debezium系列之:记录一次数据库某张表部分数据未同步到hive表的原因

Debezium系列之:记录一次数据库某张表部分数据未同步到hive表的原因 一、背景二、查找数据丢失流程三、数据丢失原因四、解决方法一、背景 反馈mysql数据库中某张表的数据没有同步到hive中,现在需要排查定位下原因数据丢失一般常见需求排查的方向: 数据是否采集到hdfs上采集…...

爆破器材期刊

《爆破器材》简介   《爆破器材》自1958年创刊以来&#xff0c;深受广大读者喜爱&#xff0c;是中国兵工学会主办的中央级技术刊物&#xff0c;在国内外公开发行&#xff0c;近几年已发行到10个国家和地区。《爆破器材》杂志被美国著名检索机构《化学文摘》&#xff08;CA&a…...

Nginx Websocket 协议配置支持

前后分离的 Web 架构应用&#xff0c;在开发环境启动是可以直接连接支持 websocket 协议&#xff0c;因为没有中间件做转发处理。 当我们对前端进行编译后&#xff0c;通过 nginx 反向代理访问时&#xff0c;需要在nginx 配置文件中增加一些特定的头信息&#xff0c;让服务端识…...

【生成式对抗网络】GANs在数据生成、艺术创作,以及在增强现实和虚拟现实中的应用

一、GANs在数据生成中的应用 生成对抗网络&#xff08;Generative Adversarial Networks, GANs&#xff09;在数据生成领域具有显著的应用价值。GANs通过生成器&#xff08;Generator&#xff09;和判别器&#xff08;Discriminator&#xff09;两个相互竞争的神经网络&#x…...

网络编程(Modbus进阶)

思维导图 Modbus RTU&#xff08;先学一点理论&#xff09; 概念 Modbus RTU 是工业自动化领域 最广泛应用的串行通信协议&#xff0c;由 Modicon 公司&#xff08;现施耐德电气&#xff09;于 1979 年推出。它以 高效率、强健性、易实现的特点成为工业控制系统的通信标准。 包…...

<6>-MySQL表的增删查改

目录 一&#xff0c;create&#xff08;创建表&#xff09; 二&#xff0c;retrieve&#xff08;查询表&#xff09; 1&#xff0c;select列 2&#xff0c;where条件 三&#xff0c;update&#xff08;更新表&#xff09; 四&#xff0c;delete&#xff08;删除表&#xf…...

FFmpeg 低延迟同屏方案

引言 在实时互动需求激增的当下&#xff0c;无论是在线教育中的师生同屏演示、远程办公的屏幕共享协作&#xff0c;还是游戏直播的画面实时传输&#xff0c;低延迟同屏已成为保障用户体验的核心指标。FFmpeg 作为一款功能强大的多媒体框架&#xff0c;凭借其灵活的编解码、数据…...

【Redis技术进阶之路】「原理分析系列开篇」分析客户端和服务端网络诵信交互实现(服务端执行命令请求的过程 - 初始化服务器)

服务端执行命令请求的过程 【专栏简介】【技术大纲】【专栏目标】【目标人群】1. Redis爱好者与社区成员2. 后端开发和系统架构师3. 计算机专业的本科生及研究生 初始化服务器1. 初始化服务器状态结构初始化RedisServer变量 2. 加载相关系统配置和用户配置参数定制化配置参数案…...

在Ubuntu中设置开机自动运行(sudo)指令的指南

在Ubuntu系统中&#xff0c;有时需要在系统启动时自动执行某些命令&#xff0c;特别是需要 sudo权限的指令。为了实现这一功能&#xff0c;可以使用多种方法&#xff0c;包括编写Systemd服务、配置 rc.local文件或使用 cron任务计划。本文将详细介绍这些方法&#xff0c;并提供…...

Neo4j 集群管理:原理、技术与最佳实践深度解析

Neo4j 的集群技术是其企业级高可用性、可扩展性和容错能力的核心。通过深入分析官方文档,本文将系统阐述其集群管理的核心原理、关键技术、实用技巧和行业最佳实践。 Neo4j 的 Causal Clustering 架构提供了一个强大而灵活的基石,用于构建高可用、可扩展且一致的图数据库服务…...

vue3 定时器-定义全局方法 vue+ts

1.创建ts文件 路径&#xff1a;src/utils/timer.ts 完整代码&#xff1a; import { onUnmounted } from vuetype TimerCallback (...args: any[]) > voidexport function useGlobalTimer() {const timers: Map<number, NodeJS.Timeout> new Map()// 创建定时器con…...

现代密码学 | 椭圆曲线密码学—附py代码

Elliptic Curve Cryptography 椭圆曲线密码学&#xff08;ECC&#xff09;是一种基于有限域上椭圆曲线数学特性的公钥加密技术。其核心原理涉及椭圆曲线的代数性质、离散对数问题以及有限域上的运算。 椭圆曲线密码学是多种数字签名算法的基础&#xff0c;例如椭圆曲线数字签…...

微服务商城-商品微服务

数据表 CREATE TABLE product (id bigint(20) UNSIGNED NOT NULL AUTO_INCREMENT COMMENT 商品id,cateid smallint(6) UNSIGNED NOT NULL DEFAULT 0 COMMENT 类别Id,name varchar(100) NOT NULL DEFAULT COMMENT 商品名称,subtitle varchar(200) NOT NULL DEFAULT COMMENT 商…...

涂鸦T5AI手搓语音、emoji、otto机器人从入门到实战

“&#x1f916;手搓TuyaAI语音指令 &#x1f60d;秒变表情包大师&#xff0c;让萌系Otto机器人&#x1f525;玩出智能新花样&#xff01;开整&#xff01;” &#x1f916; Otto机器人 → 直接点明主体 手搓TuyaAI语音 → 强调 自主编程/自定义 语音控制&#xff08;TuyaAI…...