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

news/2024/7/25 21:55:36/文章来源:https://blog.csdn.net/LNsupermali/article/details/139130571

Problem: 106. 从中序与后序遍历序列构造二叉树

文章目录

  • 题目描述
  • 思路
  • 复杂度
  • Code

题目描述

在这里插入图片描述在这里插入图片描述

思路

具体思路参考:
Problem: 力扣105. 从前序与中序遍历序列构造二叉树

再后序遍历中:每次取int rootVal = postorder[postEnd];构造根节点;左子树的范围是build(inorder, inStart, index - 1, postorder, postStart, postStart + leftSize - 1);右子树范围为build(inorder, index + 1, inEnd, postorder, postStart + leftSize, postEnd - 1)

复杂度

时间复杂度:

O ( n ) O(n) O(n);其中 n n n为树节点的个数

空间复杂度:

O ( h e i g h ) O(heigh) O(heigh);其中 h e i g h t height height为树的高度

Code

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {Map<Integer, Integer> valToIndex = new HashMap<>();public TreeNode buildTree(int[] inorder, int[] postorder) {for (int i = 0; i < inorder.length; ++i) {valToIndex.put(inorder[i], i);}return build(inorder, 0, inorder.length - 1,postorder, 0, postorder.length - 1);}TreeNode build(int[] inorder, int inStart, int inEnd, int[] postorder, int postStart, int postEnd) {if (inStart > inEnd) {return null;}// The value of the  root node is the last element of the post-order traversal groupint rootVal = postorder[postEnd];// rootVal traverses the index in the group in medium orderint index = valToIndex.get(rootVal);// Number of nodes in the left subtreeint leftSize = index - inStart;TreeNode root = new TreeNode(rootVal);root.left = build(inorder, inStart, index - 1, postorder, postStart, postStart + leftSize - 1);root.right = build(inorder, index + 1, inEnd, postorder, postStart + leftSize, postEnd - 1);return root;}
}

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

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

相关文章

Pytorch环境配置2.0.1+ Cuda11.7

查找cuda、cudnn、Pytorch(GPU)及cuda和NVIDIA显卡驱动对应关系 查询可支持的最高cuda版本 nvidia-smi查看支持的cuda的版本 CUDA版本对应表 我的显卡驱动是Driver Version&#xff1a;535.40.&#xff0c;那么左边对应的CUDA都可以兼容 右上角为CUDA 版本&#xff0c;可以看…

java面试框架篇(Spring常见问题、SpringBoot、SpringMVC、mybatis经典问题、SpringCloud组件)

文章目录 面试专题-java框架篇1. spring常见问题1.1. spring是什么?1.2. 谈谈你对AOP的理解1.3. 谈谈你对IOC的理解1.4. Spring Boot、 Spring MVC和Spring有什么区别1.5. spring bean 生命周期1.6. spring事务传播机制有哪些?1.7. 循环依赖1.8. spring框架中使用了哪些设计模…

作为一名前端工程师,该如何控制高并发请求呢?「如果有更好的方案,欢迎讨论」

假如现在有几十、上百个请求&#xff0c;我们该如何去控制这么高的并发呢&#xff1f; 给你一分钟时间&#xff0c;稍作思考 &#xff5e; &#x1f914; 此场景有很多&#xff0c;比如 图片或文件批量下载、RSSHub高速抓取内容。。。 第一想法是不是请求池&#xff01;&…

虚拟化技术[1]之服务器虚拟化

文章目录 虚拟化技术简介数据中心虚拟化 服务器虚拟化服务器虚拟化层次寄居虚拟化裸机虚拟化VMM无法直接捕获特权指令解决方案 服务器虚拟化底层实现CPU虚拟化内存虚拟化I/O设备虚拟化 虚拟机迁移虚拟机动态迁移迁移内容&#xff1a;内存迁移迁移内容&#xff1a;网络资源迁移迁…

NSSCTF | [SWPUCTF 2021 新生赛]no_wakeup

打开题目后&#xff0c;点击三个&#xff1f;&#xff0c;发现是一个php序列化脚本 <?phpheader("Content-type:text/html;charsetutf-8"); error_reporting(0); show_source("class.php");class HaHaHa{public $admin;public $passwd;public function…

2024第三届AIGC开发者大会圆桌论坛:AI Agent中国落地发展现状及多模态结合具身智能的发展展望

在2024年第三届AIGC开发者大会上&#xff0c;多位业内专家齐聚一堂&#xff0c;共同探讨了AI Agent在中国的落地发展现状以及多模态结合具身智能的发展前景。本次圆桌论坛的嘉宾包括&#xff1a; Fast JP作者于金龙Agent创始人莫西莫必胜作者秦瑞January Agent创始人李晨 多模…

Cesium For Unity 在Unity中无法下载的问题

Unity 下载失败&#xff0c;提供百度网盘“com.cesium.unity-1.10.0.tgz”下载链接 链接&#xff1a;https://pan.baidu.com/s/1PybXQ8EvkRofOKD6rSN66g?pwd1234 提取码&#xff1a;1234 导入方法&#xff1a; 1.打开PackageManager;Window-PackageManager 2.在PackageMan…

Vue3:封装Table 表格组件

组件官网 elementPlus : 点击跳转 封装组件 创建新的组件文件: Table.vue <!-- PropTableS &#xff1a; 父组件传递过来的数据 (对象)PropTableS.tables : 父组件传递的对象中 存放表格每行显示的数据PropTableS.keyS &#xff1a; 父组件传递过来的对象&#xff0c;里…

Golang实现递归复制文件夹

代码 package zdpgo_fileimport ("errors""os""path/filepath""strings" )// CopyDir 复制文件夹 // param srcPath 源文件夹 // param desPath 目标文件夹 // return error 错误信息 func CopyDir(srcPath, desPath string) error {…

6岁开始学习打字,10岁学懂文字编程

​你们有没有想过打字速度会影响Coding 编程能力&#xff1f; 疫情期间&#xff0c;全国中小学均不定期停止面授课程&#xff0c;改为网上教学。顷刻之间&#xff0c;电脑、智能手机等即时通讯软件成为每日学习的「良师益友」&#xff0c;常伴左右。 同时&#xff0c;学生也由…

每天五分钟深度学习框架PyTorch:创建具有特殊值的tensor张量

本文重点 tensor张量是一个多维数组,本节课程我们将学习一些pytorch中已经封装好的方法,使用这些方法我们可以快速创建出具有特殊意义的tensor张量。 创建一个值为空的张量 import torch import numpy as np a=torch.empty(1) print(a) print(a.dim()) print(s.shape) 如图…

本地部署 MiniCPM-Llama3-V 2.5

本地部署 MiniCPM-Llama3-V 2.5 0. 引言1. 性能评估2. 典型示例3. 本地部署4. 运行 WebUI Demo5. vLLM 部署 0. 引言 MiniCPM-Llama3-V 2.5 是 MiniCPM-V 系列的最新版本模型&#xff0c;基于 SigLip-400M 和 Llama3-8B-Instruct 构建&#xff0c;共 8B 参数量&#xff0c;相较…

Linux java jni调用C++封装动态库

由于项目中java需要调用第三方提供的C动态库&#xff1b;由于第三方动态库传入的参数较多&#xff0c;还伴随着指针传入操作&#xff0c;导致java调用极为不便&#xff01;因此催生出对于第三方的C动态库进行二次封装。java调用只需按结构传入一个结构化的string即可。话不多说…

CSS文本粒子动画特效之爱心粒子文字特效-Canvas

1. 效果图 2.完整代码 <!DOCTYPE html> <html lang"en"><head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-width, initial-scale1.0"><style>body,html {margin: 0;paddin…

嵌入式学习——3——UDP TFTP简易文件传输

tftp协议概述 简单文件传输协议&#xff0c;适用于在网络上进行文件传输的一套标准协议&#xff0c;使用UDP传输 特点&#xff1a; 是应用层协议 基于UDP协议实现 数据传输模式 octet&#xff1a;二进制模式&#xff08;常用&#xff09; mail&#xff1a;已经不再支持 TFTP通信…

【Spring】深入学习AOP编程思想的实现原理和优势

【切面编程】深入学习AOP编程思想的实现原理和优势 前言AOP的由来及AOP与代理的关系AOP的实现方式详解静态代理动态代理 AOP的应用场景记录日志权限控制数据库事务控制缓存处理异常处理监控管理 AOP的底层实现全流程解析Spring AOP的简介动态代理的实现原理Spring AOP的实现原理…

易查分小程序 学生成绩管理小程序

亲爱的老师们&#xff0c;是不是每次成绩公布后&#xff0c;家长们的连环夺命call让你头大&#xff1f;担心孩子们的成绩信息安全&#xff0c;又想快速分享给家长&#xff0c;这可咋整&#xff1f;别急&#xff0c;易查分小程序来帮忙啦&#xff01; 安全有保障 智能验证码&a…

K8S集群监控方案之Prometheus+kube-state-metrics+Grafana

序言 | Prometheus 中文文档 方案简单架构图 一、部署kube-state-metrics 1、部署文件下载 地址 kube-state-metrics/examples/standard at main kubernetes/kube-state-metrics GitHub 2、修改下载的文件 2.1、修改镜像 原镜像可能下载不了&#xff0c;这里修改deploy…

43、Flink 的 Window Join 详解

1.Window Join a&#xff09;概述 Window join 作用在两个流中有相同 key 且处于相同窗口的元素上&#xff0c;窗口可以通过 window assigner 定义&#xff0c;并且两个流中的元素都会被用于计算窗口的结果。 两个流中的元素在组合之后&#xff0c;会被传递给用户定义的 Joi…

数据结构算法题day03

数据结构算法题day03 题目 题目 2.设计一个高效算法&#xff0c;将顺序表L的所有元素逆置&#xff0c;要求算法的空间复杂度为O(1)算法思想&#xff1a; 1、常规的解法&#xff1a; Void reverse (sqlist &L){Elemtype temp; //辅助变量for(i 0,i < L.length; i){temp…