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)}")
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/373282.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

python脚本“文档”撰写——“诱骗”ai撰写“火火的动态”python“自动”脚本文档

“火火的动态”python“自动”脚本文档&#xff0c;又从ai学习搭子那儿“套”来&#xff0c;可谓良心质量&#x1f44d;&#x1f44d;。 (笔记模板由python脚本于2024年07月07日 15:15:33创建&#xff0c;本篇笔记适合喜欢钻研python和页面源码的coder翻阅) 【学习的细节是欢悦…

PHP智慧门店微信小程序系统源码

&#x1f50d;【引领未来零售新风尚】&#x1f50d; &#x1f680;升级启航&#xff0c;智慧零售新篇章&#x1f680; 告别传统门店的束缚&#xff0c;智慧门店v3微信小程序携带着前沿科技与人性化设计&#xff0c;正式启航&#xff01;这个版本不仅是对过往功能的全面优化&a…

Java面试八股之MySQL的redo log和undo log

MySQL的redo log和undo log 在MySQL的InnoDB存储引擎中&#xff0c;redo log和undo log是两种重要的日志&#xff0c;它们各自服务于不同的目的&#xff0c;对数据库的事务处理和恢复机制至关重要。 Redo Log&#xff08;重做日志&#xff09; 功能 redo log的主要作用是确…

伯克利、斯坦福和CMU面向具身智能端到端操作联合发布开源通用机器人Policy,可支持多种机器人执行多种任务

不同于LLM或者MLLM那样用于上百亿甚至上千亿参数量的大模型&#xff0c;具身智能端到端大模型并不追求参数规模上的大&#xff0c;而是指其能吸收大量的数据&#xff0c;执行多种任务&#xff0c;并能具备一定的泛化能力&#xff0c;如笔者前博客里的RT1。目前该领域一个前沿工…

CentOS6禁止锁屏

在电源中设置后还是会锁屏, 原因是有屏幕保护程序 电源管理都 “从不” 一些AI的回答 在CentOS 6系统中&#xff0c;如果你想要禁用锁屏功能&#xff0c;可以编辑/etc/kbd/config文件。这个文件通常包含了键盘相关的设置&#xff0c;包括密码策略和屏幕锁定选项。 首先打开终…

javascript高级部分笔记

javascript高级部分 Function方法 与 函数式编程 call 语法&#xff1a;call([thisObj[,arg1[, arg2[, [,.argN]]]]]) 定义&#xff1a;调用一个对象的一个方法&#xff0c;以另一个对象替换当前对象。 说明&#xff1a;call 方法可以用来代替另一个对象调用一个方法。cal…

C语言程序题(一)

一.三个整数从大到小输出 首先做这个题目需要知道理清排序的思路&#xff0c;通过比较三个整数的值&#xff0c;使之从大到小输出。解这道题有很多方法我就总结了两种方法&#xff1a;一是通过中间变量比较和交换&#xff0c;二是可以用冒泡排序法&#xff08;虽然三个数字排序…

微信小程序引入自定义子组件报错,在 C:/Users/***/WeChatProjects/miniprogram-1/components/路径下***

使用原生小程序开发时候&#xff0c;会报下面的错误&#xff0c; [ pages/button/button.json 文件内容错误] pages/button/button.json: [“usingComponents”][“second-component”]: “…/…/components/second-child/index”&#xff0c;在 C:/Users/***/WeChatProjects/m…

Infinitar链游新发展新机遇

区块链游戏市场在近年来经历了显著增长&#xff0c;吸引了大量的投资和关注。随着加密货币和NFT&#xff08;非同质化代币&#xff09;概念的普及&#xff0c;越来越多的投资者、游戏开发者和看到了区块链技术在游戏领域的应用潜力&#xff0c;纷纷涌入市场。区块链游戏的用户量…

电脑虚拟摄像头怎么使用?电脑摄像头可以被虚拟摄像头替代吗?8款推荐!

在数字化日益普及的今天&#xff0c;视频通话和在线会议已成为我们生活和工作中不可或缺的一部分。然而&#xff0c;当我们的电脑没有配备摄像头&#xff0c;或摄像头出现故障时&#xff0c;我们可能会面临一些不便。这时&#xff0c;电脑虚拟摄像头便成为了一个实用的解决方案…

Python中JSON处理技术的详解

引言 JSON&#xff08;JavaScript Object Notation&#xff09;作为当前最流行的数据传输格式&#xff0c;在Python中也有多种实现方式。由于JSON的跨平台性和简便易用性&#xff0c;它在数据交互中被广泛应用。本文将重点讨论如何熟练应用Python的JSON库&#xff0c;将JSON数…

概率论习题

泊松分布习题 假设你在医院值班&#xff0c;每天需要安保人员出动的次数N~P(1),则关于任一天安保人员出动次数&#xff1a; A&#xff1a;出动一次的概率是多少 B&#xff1a;出动次数小于等于一次的概率为 C&#xff1a;出动次数小于一次的概率为 D&#xff1a;若随机事件发生…

在表格中选中el-radio后, 怎么获取选中的这一行的所有数据?

演示: 图中, 选中这行数据后, 怎么获取到当前的数据? 代码: <tr v-for"item in gridData"><td><input type"radio" v-model"checkout" change"getDateFn" :data-type"item.articleType" :data-channelNam…

UE5 视频播放(自动播放和自动清除MediaTexture)

媒体播放器的打开时播放和媒体纹理的自动清除 。 在UE5开发视频播放时&#xff0c;遇到了闪帧的现象。合理选择这两个功能可解决。

71.WEB渗透测试-信息收集- WAF、框架组件识别(11)

免责声明&#xff1a;内容仅供学习参考&#xff0c;请合法利用知识&#xff0c;禁止进行违法犯罪活动&#xff01; 内容参考于&#xff1a; 易锦网校会员专享课 上一个内容&#xff1a;70.WEB渗透测试-信息收集- WAF、框架组件识别&#xff08;10&#xff09;-CSDN博客 如果有…

基于门控循环单元 GRU 实现股票单变量时间序列预测(PyTorch版)

前言 系列专栏:【深度学习&#xff1a;算法项目实战】✨︎ 涉及医疗健康、财经金融、商业零售、食品饮料、运动健身、交通运输、环境科学、社交媒体以及文本和图像处理等诸多领域&#xff0c;讨论了各种复杂的深度神经网络思想&#xff0c;如卷积神经网络、循环神经网络、生成对…

深入了解线程锁的使用及锁的本质

文章目录 线程锁的本质局部锁的使用 锁的封装及演示线程饥饿问题 线程加锁本质可重入和线程安全死锁问题 根据前面内容的概述, 上述我们已经知道了在linux下关于线程封装和线程互斥,锁的相关的概念, 下面就来介绍一下关于线程锁的一些其他概念. 线程锁的本质 当这个锁是全局的…

6800和8080单片机读写时序和液晶屏接口

前言&#xff1a; 随着单片机发展&#xff0c;集成度越来越高&#xff0c;因此目前单片机较少使用RD和WR信号操作外设&#xff0c;因此很多时候&#xff0c;变成了6800和8080单片机读写液晶屏了。早期的读写本质上是对一个地址进行即时的操作&#xff0c;现在可能是等数据送到…

打开excel时弹出stdole32.tlb

问题描述 打开excel时弹出stdole32.tlb 如下图&#xff1a; 解决方法 打开 Microsoft Excel 并收到关于 stdole32.tlb 的错误提示时&#xff0c;通常意味着与 Excel 相关的某个组件或类型库可能已损坏或不兼容。 stdole32.tlb 是一个用于存储自动化对象定义的类型库&#x…

PowerShell install 一键部署mysql 9.0.0

mysql 前言 MySQL 是一个基于 SQL(Structured Query Language)的数据库系统,SQL 是一种用于访问和管理数据库的标准语言。MySQL 以其高性能、稳定性和易用性而闻名,它被广泛应用于各种场景,包括: Web 应用程序:许多动态网站和内容管理系统(如 WordPress)使用 MySQL 存…