LeetCode Hot100 105.从前序与中序遍历序列构造二叉树
题目:给定两个整数数组 preorder 和 inorder ,其中 preorder 是二叉树的先序遍历, inorder 是同一棵树的中序遍历,请构造二叉树并返回其根节点。
代码:
class Solution {private Map<Integer, Integer> indexMap;public TreeNode myBuildTree(int[] preorder, int[] inorder, int preorder_left, int preorder_right, int inorder_left, int inorder_right) {if (preorder_left > preorder_right) {return null;}// 前序遍历中的第一个节点就是根节点int preorder_root = preorder_left;// 在中序遍历中定位根节点int inorder_root = indexMap.get(preorder[preorder_root]);// 先把根节点建立出来TreeNode root = new TreeNode(preorder[preorder_root]);// 得到左子树中的节点数目int size_left_subtree = inorder_root - inorder_left;// 递归地构造左子树,并连接到根节点// 先序遍历中「从 左边界+1 开始的 size_left_subtree」个元素就对应了中序遍历中「从 左边界 开始到 根节点定位-1」的元素root.left = myBuildTree(preorder, inorder, preorder_left + 1, preorder_left + size_left_subtree, inorder_left, inorder_root - 1);// 递归地构造右子树,并连接到根节点// 先序遍历中「从 左边界+1+左子树节点数目 开始到 右边界」的元素就对应了中序遍历中「从 根节点定位+1 到 右边界」的元素root.right = myBuildTree(preorder, inorder, preorder_left + size_left_subtree + 1, preorder_right, inorder_root + 1, inorder_right);return root;}public TreeNode buildTree(int[] preorder, int[] inorder) {int n = preorder.length;// 构造哈希映射,帮助我们快速定位根节点indexMap = new HashMap<Integer, Integer>();for (int i = 0; i < n; i++) {indexMap.put(inorder[i], i);}return myBuildTree(preorder, inorder, 0, n - 1, 0, n - 1);}
}

题目:给定两个整数数组 inorder 和 postorder ,其中 inorder 是二叉树的中序遍历, postorder 是同一棵树的后序遍历,请你构造并返回这颗 二叉树 。
中序 + 后序 构建 二叉树
class Solution {static int[] pos;static Map<Integer, Integer> map;public TreeNode buildTree(int[] inorder, int[] postorder) {int posLen = postorder.length;int inLen = inorder.length;pos = postorder;map = new HashMap<>();for (int i = 0; i < inLen; i++) {map.put(inorder[i], i);}return buildTree(0, posLen - 1, 0, inLen - 1);}public TreeNode buildTree(int inL, int inR, int posL, int posR) {if (posL > posR || inL > inR) {return null;}int val = pos[posR];TreeNode root = new TreeNode(val);int piv = map.get(val);int sizeL = piv - inL;int posM = posL + sizeL - 1;root.left = buildTree(inL, piv - 1, posL, posM);root.right = buildTree(piv + 1, inR, posM + 1, posR - 1);return root;}
}
// 代码同 中序+先序构建二叉树,只需要把先序的地方改成后序
class Solution {private Map<Integer, Integer> indexMap;public TreeNode myBuildTree(int[] postorder, int[] inorder, int postorder_left, int postorder_right, int inorder_left, int inorder_right) {if (postorder_left > postorder_right || inorder_left > inorder_right) {return null;}// 后序遍历中的最后一个节点就是根节点int postorder_root = postorder_right;int val = postorder[postorder_root];// 在中序遍历中定位根节点int inorder_root = indexMap.get(val);// 先把根节点建立出来TreeNode root = new TreeNode(postorder[postorder_root]);// 得到左子树中的节点数目int size_left_subtree = inorder_root - inorder_left;root.left = myBuildTree(postorder, inorder, postorder_left, postorder_left + size_left_subtree - 1, inorder_left, inorder_root - 1);root.right = myBuildTree(postorder, inorder, postorder_left + size_left_subtree, postorder_right - 1, inorder_root + 1, inorder_right);return root;}public TreeNode buildTree(int[] inorder, int[] postorder ) {int n = postorder.length;// 构造哈希映射,帮助我们快速定位根节点indexMap = new HashMap<Integer, Integer>();for (int i = 0; i < n; i++) {indexMap.put(inorder[i], i);}return myBuildTree(postorder, inorder, 0, n - 1, 0, n - 1);}}
注意:如果人家给好的函数,你把形参数位置调换了,会一直报栈溢出StackOverFlow错误!!!
相关文章:
LeetCode Hot100 105.从前序与中序遍历序列构造二叉树
题目:给定两个整数数组 preorder 和 inorder ,其中 preorder 是二叉树的先序遍历, inorder 是同一棵树的中序遍历,请构造二叉树并返回其根节点。 代码: class Solution {private Map<Integer, Integer> indexM…...
今天先水一章
水贴,可自动忽略...
网页设计作业-音乐网站首页
效果图 网盘链接 链接:https://pan.baidu.com/s/1CO4jAOY0zk1AWTx_pC3UmA?pwdfuck 提取码:fuck...
【2023 云栖】阿里云刘一鸣:Data+AI 时代大数据平台建设的思考与发布
云布道师 本文根据 2023 云栖大会演讲实录整理而成,演讲信息如下: 演讲人:刘一鸣 | 阿里云自研大数据产品负责人 演讲主题:DataAI 时代大数据平台应该如何建设 今天分享的主题是 DataAI 时代大数据平台应该如何建设࿰…...
【DP】mobiusp正在创作乐曲
输入样例1: 5 2 1 7 7 1 3 输出样例1: 2 输入样例2: 10 3 2 5 6 4 4 5 7 3 5 6 输出样例2: 1 #include<iostream> #include<cstring> #include<algorithm> #include<vector> using namespace std; typede…...
docker国内镜像加速
创建或修改 /etc/docker/daemon.json 文件,修改为如下形式 {"registry-mirrors": ["https://registry.docker-cn.com","http://hub-mirror.c.163.com","https://docker.mirrors.ustc.edu.cn"] } Docker中国区官方镜像htt…...
Calling PeopleTools APIs 调用PeopleTools API
Calling PeopleTools APIs 调用PeopleTools API You can call all of the PeopleTools APIs from an Application Engine program. When using APIs, remember that: 您可以从应用程序引擎程序调用所有PeopleTools API。使用API时,请记住: All the PeopleTools …...
强化学习,快速入门与基于python实现一个简单例子(可直接运行)
文章目录 一、什么是“强化学习”二、强化学习包括的组成部分二、Q-Learning算法三、迷宫-强化学习-Q-Learning算法的实现全部代码(复制可用)可用状态空间检查是否超出边界epsilon 的含义更新方程 总结 一、什么是“强化学习” 本文要记录的大概内容&am…...
【手写实现一个简单版的Dubbo,深刻理解RPC框架的底层实现原理】
手写实现一个简单版的Dubbo,深刻理解RPC框架的底层实现原理 RPC框架简介了解Dubbo的实现原理服务暴露服务引入服务调用 手写实现一个简单版的Dubbo服务暴露ServiceBeanProxyFactory#getInvokerProtocol#exportRegistryProtocol#export 服务引入RegistryProto#referD…...
计数问题+约瑟夫问题(map)
目录 一、计数问题 二、约瑟夫问题 一、计数问题 #include<iostream> #include<map> using namespace std; int main() {int n,x;cin>>n>>x;map<int,int>m;for(int i1;i<n;i){if(i>1 && i<10){m[i];}else{int temp i;while (…...
Maven聚合项目发布至私服指定模块
无论是从事框架开发工作还是公共服务模块开发,为了解决通用性问题,常常需要发布一些依赖组件至maven私服。然而通常我们得maven工程都是由多个模块组成得聚合工程(一个父工程下有多个模块)。 这个时候可能会面临两个窘境…...
SpringCloud 微服务全栈体系(十六)
第十一章 分布式搜索引擎 elasticsearch 六、DSL 查询文档 elasticsearch 的查询依然是基于 JSON 风格的 DSL 来实现的。 1. DSL 查询分类 Elasticsearch 提供了基于 JSON 的 DSL(Domain Specific Language)来定义查询。常见的查询类型包括࿱…...
「快学Docker」监控和日志记录容器的健康和性能
「快学Docker」监控和日志记录容器的健康和性能 1. 容器健康状态监控2. 性能监控3. 日志记录几种采集架构图 4. 监控工具和平台cAdvisor(Container Advisor)PrometheusGrafana 5. 自动化运维 1. 容器健康状态监控 方法1:需要实时监测容器的运…...
midjourney过时了?如何使用基于LCM的绘图技术画出你心中的画卷。
生成 AI 艺术在近年来迅速发展,吸引了数百万用户。然而,传统的生成 AI 艺术需要等待几秒钟或几分钟才能生成,这对于快节奏的现代社会来说并不理想。 近日,中国清华大学和 AI 代码共享平台 HuggingFace 联合开发了一项新的机器学习…...
【代码随想录】算法训练计划28
回溯 1、子集 题目: 给你一个整数数组 nums ,数组中的元素 互不相同 。返回该数组所有可能的子集(幂集)。 解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。 输入:nums [1,2,3] 输出:[[],[1],[2…...
量化交易:筹码理论的探索-筹码分布计算的实现
前言 很多朋友习惯了同花顺、大智慧等看盘软件,经常问到筹码分布如何计算。 说起来筹码分布的理论在庄股时代堪称是一个划时代产品,虽然历经level2数据、资金流统计、拆单算法与反拆单算法等新型技术的变革,庄股时代也逐渐淡出市场…...
常用Redis的键命令参考
一、DEL DEL key [key …] 删除给定的一个或多个 key 。 不存在的 key 会被忽略。 #删除单个键127.0.0.1:6379> set name zhangsan OK 127.0.0.1:6379> del name (integer) 1# 删除一个不存在的 key, 失败,没有 key 被删除127.0.0.1:6379> E…...
Lombok @With 的纯弊端及如何避免
由于是第一篇写关于 Lombok 的日志,所以有些不情愿去开门见山直接触及 With, 而要先提一提本人对 Lombok 的接触过程。 两三年之前写 Java 代码一直都是全手工打造。一个数据类,所有必须的 setter/getter, toString, hashcode() 等全体现在源代码中&…...
C语言每日一题(38)无重复字符的最长字串
力扣 3 无重复字符的最长字串 题目描述 给定一个字符串 s ,请你找出其中不含有重复字符的 最长子串 的长度。 示例 1: 输入: s "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。示例 2: 输入: s…...
Azure Machine Learning - Azure可视化图像分类操作实战
目录 一、数据准备二、创建自定义视觉资源三、创建新项目四、选择训练图像五、上传和标记图像六、训练分类器七、评估分类器概率阈值 八、管理训练迭代 在本文中,你将了解如何使用Azure可视化页面创建图像分类模型。 生成模型后,可以使用新图像测试该模型…...
Chapter03-Authentication vulnerabilities
文章目录 1. 身份验证简介1.1 What is authentication1.2 difference between authentication and authorization1.3 身份验证机制失效的原因1.4 身份验证机制失效的影响 2. 基于登录功能的漏洞2.1 密码爆破2.2 用户名枚举2.3 有缺陷的暴力破解防护2.3.1 如果用户登录尝试失败次…...
linux之kylin系统nginx的安装
一、nginx的作用 1.可做高性能的web服务器 直接处理静态资源(HTML/CSS/图片等),响应速度远超传统服务器类似apache支持高并发连接 2.反向代理服务器 隐藏后端服务器IP地址,提高安全性 3.负载均衡服务器 支持多种策略分发流量…...
【HarmonyOS 5.0】DevEco Testing:鸿蒙应用质量保障的终极武器
——全方位测试解决方案与代码实战 一、工具定位与核心能力 DevEco Testing是HarmonyOS官方推出的一体化测试平台,覆盖应用全生命周期测试需求,主要提供五大核心能力: 测试类型检测目标关键指标功能体验基…...
Spring Boot+Neo4j知识图谱实战:3步搭建智能关系网络!
一、引言 在数据驱动的背景下,知识图谱凭借其高效的信息组织能力,正逐步成为各行业应用的关键技术。本文聚焦 Spring Boot与Neo4j图数据库的技术结合,探讨知识图谱开发的实现细节,帮助读者掌握该技术栈在实际项目中的落地方法。 …...
WEB3全栈开发——面试专业技能点P2智能合约开发(Solidity)
一、Solidity合约开发 下面是 Solidity 合约开发 的概念、代码示例及讲解,适合用作学习或写简历项目背景说明。 🧠 一、概念简介:Solidity 合约开发 Solidity 是一种专门为 以太坊(Ethereum)平台编写智能合约的高级编…...
Linux 中如何提取压缩文件 ?
Linux 是一种流行的开源操作系统,它提供了许多工具来管理、压缩和解压缩文件。压缩文件有助于节省存储空间,使数据传输更快。本指南将向您展示如何在 Linux 中提取不同类型的压缩文件。 1. Unpacking ZIP Files ZIP 文件是非常常见的,要在 …...
在Mathematica中实现Newton-Raphson迭代的收敛时间算法(一般三次多项式)
考察一般的三次多项式,以r为参数: p[z_, r_] : z^3 (r - 1) z - r; roots[r_] : z /. Solve[p[z, r] 0, z]; 此多项式的根为: 尽管看起来这个多项式是特殊的,其实一般的三次多项式都是可以通过线性变换化为这个形式…...
CRMEB 中 PHP 短信扩展开发:涵盖一号通、阿里云、腾讯云、创蓝
目前已有一号通短信、阿里云短信、腾讯云短信扩展 扩展入口文件 文件目录 crmeb\services\sms\Sms.php 默认驱动类型为:一号通 namespace crmeb\services\sms;use crmeb\basic\BaseManager; use crmeb\services\AccessTokenServeService; use crmeb\services\sms\…...
【前端异常】JavaScript错误处理:分析 Uncaught (in promise) error
在前端开发中,JavaScript 异常是不可避免的。随着现代前端应用越来越多地使用异步操作(如 Promise、async/await 等),开发者常常会遇到 Uncaught (in promise) error 错误。这个错误是由于未正确处理 Promise 的拒绝(r…...
离线语音识别方案分析
随着人工智能技术的不断发展,语音识别技术也得到了广泛的应用,从智能家居到车载系统,语音识别正在改变我们与设备的交互方式。尤其是离线语音识别,由于其在没有网络连接的情况下仍然能提供稳定、准确的语音处理能力,广…...
