当前位置: 首页 > 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…...

接口测试中缓存处理策略

在接口测试中&#xff0c;缓存处理策略是一个关键环节&#xff0c;直接影响测试结果的准确性和可靠性。合理的缓存处理策略能够确保测试环境的一致性&#xff0c;避免因缓存数据导致的测试偏差。以下是接口测试中常见的缓存处理策略及其详细说明&#xff1a; 一、缓存处理的核…...

eNSP-Cloud(实现本地电脑与eNSP内设备之间通信)

说明&#xff1a; 想象一下&#xff0c;你正在用eNSP搭建一个虚拟的网络世界&#xff0c;里面有虚拟的路由器、交换机、电脑&#xff08;PC&#xff09;等等。这些设备都在你的电脑里面“运行”&#xff0c;它们之间可以互相通信&#xff0c;就像一个封闭的小王国。 但是&#…...

树莓派超全系列教程文档--(61)树莓派摄像头高级使用方法

树莓派摄像头高级使用方法 配置通过调谐文件来调整相机行为 使用多个摄像头安装 libcam 和 rpicam-apps依赖关系开发包 文章来源&#xff1a; http://raspberry.dns8844.cn/documentation 原文网址 配置 大多数用例自动工作&#xff0c;无需更改相机配置。但是&#xff0c;一…...

(二)TensorRT-LLM | 模型导出(v0.20.0rc3)

0. 概述 上一节 对安装和使用有个基本介绍。根据这个 issue 的描述&#xff0c;后续 TensorRT-LLM 团队可能更专注于更新和维护 pytorch backend。但 tensorrt backend 作为先前一直开发的工作&#xff0c;其中包含了大量可以学习的地方。本文主要看看它导出模型的部分&#x…...

在 Nginx Stream 层“改写”MQTT ngx_stream_mqtt_filter_module

1、为什么要修改 CONNECT 报文&#xff1f; 多租户隔离&#xff1a;自动为接入设备追加租户前缀&#xff0c;后端按 ClientID 拆分队列。零代码鉴权&#xff1a;将入站用户名替换为 OAuth Access-Token&#xff0c;后端 Broker 统一校验。灰度发布&#xff1a;根据 IP/地理位写…...

linux arm系统烧录

1、打开瑞芯微程序 2、按住linux arm 的 recover按键 插入电源 3、当瑞芯微检测到有设备 4、松开recover按键 5、选择升级固件 6、点击固件选择本地刷机的linux arm 镜像 7、点击升级 &#xff08;忘了有没有这步了 估计有&#xff09; 刷机程序 和 镜像 就不提供了。要刷的时…...

python爬虫:Newspaper3k 的详细使用(好用的新闻网站文章抓取和解析的Python库)

更多内容请见: 爬虫和逆向教程-专栏介绍和目录 文章目录 一、Newspaper3k 概述1.1 Newspaper3k 介绍1.2 主要功能1.3 典型应用场景1.4 安装二、基本用法2.2 提取单篇文章的内容2.2 处理多篇文档三、高级选项3.1 自定义配置3.2 分析文章情感四、实战案例4.1 构建新闻摘要聚合器…...

MySQL中【正则表达式】用法

MySQL 中正则表达式通过 REGEXP 或 RLIKE 操作符实现&#xff08;两者等价&#xff09;&#xff0c;用于在 WHERE 子句中进行复杂的字符串模式匹配。以下是核心用法和示例&#xff1a; 一、基础语法 SELECT column_name FROM table_name WHERE column_name REGEXP pattern; …...

用docker来安装部署freeswitch记录

今天刚才测试一个callcenter的项目&#xff0c;所以尝试安装freeswitch 1、使用轩辕镜像 - 中国开发者首选的专业 Docker 镜像加速服务平台 编辑下面/etc/docker/daemon.json文件为 {"registry-mirrors": ["https://docker.xuanyuan.me"] }同时可以进入轩…...

JVM暂停(Stop-The-World,STW)的原因分类及对应排查方案

JVM暂停(Stop-The-World,STW)的完整原因分类及对应排查方案,结合JVM运行机制和常见故障场景整理而成: 一、GC相关暂停​​ 1. ​​安全点(Safepoint)阻塞​​ ​​现象​​:JVM暂停但无GC日志,日志显示No GCs detected。​​原因​​:JVM等待所有线程进入安全点(如…...