106. 从中序与后序遍历序列构造二叉树 - 力扣(LeetCode)

题目描述

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

题目示例

在这里插入图片描述

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

解题思路

在这里插入图片描述

在这里插入图片描述

参考代码

class Solution {int post_idx;int[] postorder;int[] inorder;Map<Integer, Integer> idx_map = new HashMap<>();public TreeNode buildTree(int[] inorder, int[] postorder) {this.postorder = postorder;this.inorder = inorder;// 从后序遍历的最后一个元素开始post_idx = postorder.length - 1;// 建立 元素 下标 对应的哈希表int idx = 0;for(Integer val : inorder) {idx_map.put(val, idx++);}return helper(0, inorder.length - 1);}public TreeNode helper(int in_left, int in_right) {// 如果这里没有节点构造二叉树了,就结束if(in_left > in_right) {return null;}// 选择post_idx位置的元素作为当前子树根节点int root_val = postorder[post_idx];TreeNode root = new TreeNode(root_val);// 根据root所在位置分成左右两颗子树int index = idx_map.get(root_val);// 下标减一post_idx--;// 构造右子树root.right = helper(index + 1, in_right);// 构造左子树root.left = helper(in_left, index - 1);return root;}
}

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

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

相关文章

【前沿技术杂谈:多模态文档基础模型】使用多模态文档基础模型彻底改变文档 AI

【前沿技术杂谈&#xff1a;多模态文档基础模型】使用多模态文档基础模型彻底改变文档 AI 从文本到多模态模型&#xff1a;文档 AI 逐渐发展新技能。行业领先的型号Document AI 的下一步&#xff1a;开发通用和统一框架 您是否曾经被包含不同信息&#xff08;如应付账款、日期、…

k8s-常用工作负载控制器(更高级管理Pod)

一、工作负载控制器是什么&#xff1f; 二、Deploymennt控制器&#xff1a;介绍与部署应用 部署 三、Deployment控制器&#xff1a;滚动升级、零停机 方式一&#xff1a; 通个加入健康检查可以&#xff0c;看到&#xff0c;nginx容器逐个被替代&#xff0c;最终每个都升级完成&…

【k8s系列】(202402) 证书apiserver_client_certificate_expiration_seconds

apiserver_client_certificate_expiration_second证书定义的位置&#xff1a;kubernetes/staging/src/k8s.io/apiserver/pkg/authentication/request/x509/x509.go at 244fbf94fd736e94071a77a8b7c91d81163249d4 kubernetes/kubernetes (github.com) apiserver_client_certi…

【51单片机】外部中断和定时器中断

目录 中断系统中断介绍中断概念 中断结构及相关寄存器中断结构中断相关寄存器 外部中断实验外部中断配置软件设计实验现象 定时器中断定时器介绍51 单片机定时器原理51 单片机定时/计数器结构51 单片机定时/计数器的工作方式 定时器配置硬件设计软件设计实验现象 中断系统 本章…

【http】2、http request header Origin 属性、跨域 CORS、同源、nginx 反向代理、预检请求

文章目录 一、Origin 含义二、跨源资源共享&#xff1a;**Cross-Origin Resource Sharing** CORS2.1 跨域的定义2.2 功能概述2.3 场景示例2.3.1 简单请求2.3.2 Preflighted requests&#xff1a;预检请求 2.4 header2.4.1 http request header2.4.1.1 Origin2.4.1.2 Access-Con…

[每周一更]-(第86期):PostgreSQL入门学习和对比MySQL

入门学习PostgreSQL可以遵循以下步骤&#xff1a; 安装 PostgreSQL&#xff1a; 首先&#xff0c;你需要在你的计算机上安装 PostgreSQL。你可以从 PostgreSQL 官方网站 下载适合你操作系统的安装包&#xff0c;并按照官方文档的指导进行安装。 学习 SQL&#xff1a; PostgreS…

【分布式】雪花算法学习笔记

雪花算法学习笔记 来源 https://pdai.tech/md/algorithm/alg-domain-id-snowflake.html概述 雪花算法是推特开源的分布式ID生成算法&#xff0c;以划分命名空间的方式将64位分割成多个部分&#xff0c;每一个部分代表不同的含义&#xff0c;这种就是将64位划分成不同的段&…

按键扫描16Hz-单片机通用模板

按键扫描16Hz-单片机通用模板 一、按键扫描的原理1、直接检测高低电平类型2、矩阵扫描类型3、ADC检测类型二、key.c的实现1、void keyScan(void) 按键扫描函数①void FHiKey(void) 按键按下功能②void FSameKey(void) 按键长按功能③void FLowKey(void) 按键释放功能三、key.h的…

pycharm像jupyter一样在控制台查看后台变量

更新下&#xff1a;这个一劳永逸不用一个一个改 https://blog.csdn.net/Onlyone_1314/article/details/109347481 右上角运行

力扣刷题之旅:进阶篇(三)

力扣&#xff08;LeetCode&#xff09;是一个在线编程平台&#xff0c;主要用于帮助程序员提升算法和数据结构方面的能力。以下是一些力扣上的入门题目&#xff0c;以及它们的解题代码。 --点击进入刷题地址 一、动态规划&#xff08;DP&#xff09; 首先&#xff0c;让我们来…

【芯片设计- RTL 数字逻辑设计入门 14 -- 使用子模块实现三输入数的大小比较】

文章目录 三输入数的大小比较问题分析verilog codeTestBench Code综合图仿真波形图 三输入数的大小比较 在数字芯片设计中&#xff0c;通常把完成特定功能且相对独立的代码编写成子模块&#xff0c;在需要的时候再在主模块中例化使用&#xff0c;以提高代码的可复用性和设计的层…

PHP框架详解 - symfony框架

首先说一下为什么要写symfony框架&#xff0c;这个框架也属于PHP的一个框架&#xff0c;小编接触也是3年前&#xff0c;原因是小编接触Golang&#xff0c;发现symfony框架有PHP框架的东西也有Golang的东西&#xff0c;所以决定总结一下&#xff0c;有需要的同学可以参看小编的G…

【iOS分类、关联对象】如何使用关联对象给分类实现一个weak的属性

如何使用关联对象给分类实现一个weak的属性 通过关联对象objc_setAssociatedObject中的策略policy可知&#xff0c;并不支持使用weak修饰对象属性&#xff1a; typedef OBJC_ENUM(uintptr_t, objc_AssociationPolicy) {OBJC_ASSOCIATION_ASSIGN 0, //assignOBJC_ASSOCIATION…

蓝桥杯每日一练(python)B组

###来源于dotcpp的蓝桥杯真题 题目 2735: 蓝桥杯2022年第十三届决赛真题-取模&#xff08;Python组&#xff09; 给定 n, m &#xff0c;问是否存在两个不同的数 x, y 使得 1 ≤ x < y ≤ m 且 n mod x n mod y 。 输入格式&#xff1a; 输入包含多组独立的询问。 第一…

【Git】Windows下通过Docker安装GitLab

私有仓库 前言基本思路拉取镜像创建挂载目录创建容器容器启动成功登录仓库设置中文更改密码人员审核配置邮箱 前言 由于某云存在人数限制&#xff0c;这个其实很好理解&#xff0c;毕竟使用的是云服务器&#xff0c;人家也是要交钱的。把代码完全放在别人的服务器上面&#xf…

每日五道java面试题之java基础篇(二)

第一题. 为什么说 Java 语⾔“编译与解释并存”&#xff1f; ⾼级编程语⾔按照程序的执⾏⽅式分为编译型和解释型两种。 简单来说&#xff0c;编译型语⾔是指编译器针对特定的操作系统将源代码⼀次性翻译成可被该平台执⾏的机器码&#xff1b;解释型语⾔是指解释器对源程序逐…

初识文件包含漏洞

目录 什么是文件包含漏洞&#xff1f; 文件包含的环境要求 常见的文件包含函数 PHP伪协议 file://协议 php://协议 php://filter php://input zip://、bzip2://、zlib://协议 zip:// bzip2:// zlib:// data://协议 文件包含漏洞演示 案例1&#xff1a;php://inp…

Linux下库函数、静态库与动态库

库函数 什么是库 库是二进制文件, 是源代码文件的另一种表现形式, 是加了密的源代码; 是一些功能相近或者是相似的函数的集合体. 使用库有什么好处 提高代码的可重用性, 而且还可以提高程序的健壮性;可以减少开发者的代码开发量, 缩短开发周期. 库制作完成后, 如何给用户…

Java编程构建高效二手交易平台

✍✍计算机编程指导师 ⭐⭐个人介绍&#xff1a;自己非常喜欢研究技术问题&#xff01;专业做Java、Python、微信小程序、安卓、大数据、爬虫、Golang、大屏等实战项目。 ⛽⛽实战项目&#xff1a;有源码或者技术上的问题欢迎在评论区一起讨论交流&#xff01; ⚡⚡ Java实战 |…

Python爬虫实战:抓取猫眼电影排行榜top100#4

爬虫专栏系列&#xff1a;http://t.csdnimg.cn/Oiun0 抓取猫眼电影排行 本节中&#xff0c;我们利用 requests 库和正则表达式来抓取猫眼电影 TOP100 的相关内容。requests 比 urllib 使用更加方便&#xff0c;而且目前我们还没有系统学习 HTML 解析库&#xff0c;所以这里就…