力扣labuladong——一刷day32
提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档
文章目录
- 前言
- 一、力扣654. 最大二叉树
- 二、力扣105. 从前序与中序遍历序列构造二叉树
- 三、力扣106. 从中序与后序遍历序列构造二叉树
- 四、力扣889. 根据前序和后序遍历构造二叉树
前言
二叉树解题的思维模式分两类: 1、是否可以通过遍历一遍二叉树得到答案?如果可以,用一个 traverse 函数配合外部变量来实现,这叫「遍历」的思维模式。 2、是否可以定义一个递归函数,通过子问题(子树)的答案推导出原问题的答案?如果可以,写出这个递归函数的定义,并充分利用这个函数的返回值,这叫「分解问题」的思维模式。 无论使用哪种思维模式,你都需要思考: 如果单独抽出一个二叉树节点,它需要做什么事情?需要在什么时候(前/中/后序位置)做?其他的节点不用你操心,递归函数会帮你在所有节点上执行相同的操作。
一、力扣654. 最大二叉树
/*** 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 {public TreeNode constructMaximumBinaryTree(int[] nums) {return fun(nums, 0, nums.length-1);}public TreeNode fun(int[] nums, int low, int high){if(low > high){return null;}int index = low;for(int i = low+1; i <= high; i ++){if(nums[i] > nums[index]){index = i;}}TreeNode cur = new TreeNode(nums[index]);TreeNode l = fun(nums,low,index-1);TreeNode r = fun(nums,index+1,high);cur.left = l;cur.right = r;return cur;}
}
二、力扣105. 从前序与中序遍历序列构造二叉树
/*** 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 {public TreeNode buildTree(int[] preorder, int[] inorder) {return fun(preorder, inorder, 0, preorder.length-1, 0, inorder.length-1);}public TreeNode fun(int[] preorder, int[] inorder, int preLeft,int preRight,int inPre,int inRight){if(preLeft > preRight || inPre > inRight){return null;}TreeNode root = new TreeNode(preorder[preLeft]);int len = 0;for(int i = inPre; i <= inRight; i ++){if(inorder[i] == preorder[preLeft]){len = i - inPre;break;}}root.left = fun(preorder, inorder, preLeft+1, preLeft+len, inPre, inPre+len-1);root.right = fun(preorder, inorder, preLeft+len+1,preRight, inPre+len+1,inRight);return root;}
}
三、力扣106. 从中序与后序遍历序列构造二叉树
/*** 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> invail;public TreeNode buildTree(int[] inorder, int[] postorder) {invail = new HashMap<>();for(int i = 0; i < inorder.length; i ++){invail.put(inorder[i],i);}return fun(inorder, postorder, 0, postorder.length-1,0,inorder.length-1);}public TreeNode fun(int[] inorder, int[] postorder, int postLeft, int postRight, int inLeft, int inRight){if(postLeft > postRight || inLeft > inRight){return null;}TreeNode root = new TreeNode(postorder[postRight]);int index = invail.get(postorder[postRight]);int len = index - inLeft;root.left = fun(inorder, postorder, postLeft, postLeft+len-1,inLeft, index-1);root.right = fun(inorder, postorder, postLeft+len,postRight-1,index+1,inRight);return root;}
}
四、力扣889. 根据前序和后序遍历构造二叉树
/*** 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> invail;public TreeNode constructFromPrePost(int[] preorder, int[] postorder) {invail = new HashMap<>();for(int i = 0; i < postorder.length; i ++){invail.put(postorder[i],i);}return fun(preorder,postorder,0,preorder.length-1,0,postorder.length-1);}public TreeNode fun(int[] preorder, int[] postorder, int preLeft, int preRight,int postLeft,int postRight){if(preLeft > preRight || postLeft > postRight){return null;}TreeNode cur = new TreeNode(preorder[preLeft]);if(preLeft == preRight)return cur;int index = invail.get(preorder[preLeft+1]);int len = index - postLeft+1;cur.left = fun(preorder, postorder, preLeft+1, preLeft+len, postLeft, index);cur.right = fun(preorder, postorder, preLeft+len+1,preRight,index+1,postRight-1);return cur;}
}
相关文章:
力扣labuladong——一刷day32
提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 文章目录 前言一、力扣654. 最大二叉树二、力扣105. 从前序与中序遍历序列构造二叉树三、力扣106. 从中序与后序遍历序列构造二叉树四、力扣889. 根据前序和后序遍历构造二叉…...
Day01_《MySQL索引与性能优化》摘要
一、资料 视频:《尚硅谷MySQL数据库高级,mysql优化,数据库优化》—周阳 其他博主的完整笔记:MySQL 我的笔记:我的笔记只总结了视频p14-p46部分,因为只有这部分是讲解了MySQL的索引与explain语句分析优化…...
BMS系统项目
1、通过电压监测是否冲满,通过电压可以监测是否放完电 电池得参数 单体过压(充满电) 过压恢复(百分之90多) 欠压保护(百分之几得电,快关机了) 欠压恢复(就是欠压之上…...
sql server 多行数据合并一行显示
在 SQL Server 中,可以使用 STUFF 和 FOR XML PATH 进行多行合并成一行。例如,假设有一个表名为 orders ,其中包含订单号和产品名称: order_idproduct_name1Product A1Product B2Product C2Product D 以下查询将在 order_id 列上…...
「我的AIGC咒语库:分享和AI对话交流的秘诀——如何利用Prompt和AI进行高效交流?」
文章目录 每日一句正能量前言基础介绍什么是Prompt?什么是 Prompt Engineering?为什么需要 Prompt Engineering?如何进行 Prompt Engineering?Prompt的基本原则Prompt的编写模式AI 可以帮助程序员做什么?技术知识总结拆解任务阅读…...
强国有我助力苔花绽放 | 爱心捐赠仪式在西安顺利举办
2023年11月2日,由中国儿童中心、全国少年儿童“双有”主题教育活动组委会、中华少年儿童慈善救助基金会强国有我项目主办,陕西省青少年宫协会、陕西省妇女儿童活动中心、陕西回归儿童救助中心承办的“苔花绽放”事实无人抚养儿童关爱计划捐赠仪式在陕西回…...
Flink SQL -- CheckPoint
1、开启CheckPoint checkpoint可以定时将flink任务的状态持久化到hdfs中,任务执行失败重启可以保证中间结果不丢失 # 修改flink配置文件 vim flink-conf.yaml# checkppint 间隔时间 execution.checkpointing.interval: 1min # 任务手动取消时保存checkpoint execu…...
Load-balanced-online-OJ-system 负载均衡的OJ系统项目
前言 那么这里博主先安利一些干货满满的专栏了! 首先是博主的高质量博客的汇总,这个专栏里面的博客,都是博主最最用心写的一部分,干货满满,希望对大家有帮助。 高质量博客汇总 本项目Github地址 - Load-balanced-o…...
ES6 导入导出
ES6 导入导出 ES6引入了原生的模块化支持,使得JavaScript代码可以被划分为可重用的模块。这些模块可以导出部分代码(如函数、对象、类等),并被其他模块导入使用。 export 命名导出(Named Exports) 可以从…...
【Liunx】部署Ansible自动化运维工具
Ansible自动化运维工具 概述安装部署1.通过yum下载Ansible2.对自己做免密配置3.修改ansiable host配置对服务器进行分组4.测试:对所有服务器进行ping命令5.写playbook6.执行我们写的playbook脚本7.验证 概述 ansible是新出现的自动化运维工具,基于Pytho…...
Python的基础语法
1. 注释:在Python中,使用井号(#)表示单行注释,三个单引号()或三个双引号(""")表示多行注释。 2. 变量:在Python中,不需要声明变量…...
Skywalking流程分析_8(拦截器插件的加载)
前言 在之前的文章中我们将,静态方法、构造方法、实例方法的增强逻辑都分析完毕,但在增强前,对于拦截类的加载是至关重要的,下面我们就来详细的分析 增强插件的加载 静态方法增强前的加载 //clazz 要修改的字节码的原生类 Sta…...
智能AI系统ChatGPT网站源码+支持OpenAI DALL-E3文生图+支持ai绘画(Midjourney)/支持GPT全模型+国内AI全模型
一、AI创作系统 SparkAi创作系统是基于OpenAI很火的ChatGPT进行开发的Ai智能问答系统和Midjourney绘画系统,支持OpenAI-GPT全模型国内AI全模型。本期针对源码系统整体测试下来非常完美,可以说SparkAi是目前国内一款的ChatGPT对接OpenAI软件系统。那么如…...
腾讯云服务器可用区是什么意思?可用区选择方法
腾讯云服务器可用区是什么意思?云服务器可用区如何选择?可用区是指在同一个地域内电力和网络相互独立的区域,可用区可以做到故障隔离,所以可用区存在的意义在于构建高可用、高容灾应用,将应用部署在不同可用区内&#…...
Jupyter运行显存爆炸,明明上一个单元格已经运行完毕为什么还是会炸?
问题再现 上一个单元格运行完了train(),我想要用模型输出做点东西,可是提醒我显存不够; 在命令行中查看显存占用情况,发现4张卡都占满了,可真是太厉害了! 解决方案 查看原来写的validate(),发…...
【ICE】webrtc lite 1:cmake构建
p2ptransportchannel 是 ICE 实现基于此实现了DTLTransport而前者是独立的模块。依赖库较少主要是ssl absl OpenSSL Protobuf 可选 absl webrtc 不支持大端 :big endian architectures defined in WebRTC’s arch.h D_WINSOCKAPI_ 用来做啥? 以下编译选项: add_compile_opti…...
国内最受欢迎电商API接口调用淘宝商品详情API接口数据
国内实用的API接口 国内最受欢迎的7大API供应平台对比和介绍 本文将介绍7款API供应平台:聚合数据、百度APIStore、Apix、数说聚合、通联数据、HaoService、datasift 。排名不分先后! 免费实用的API接口 第一部分 1、电商数据(API数据接口_开…...
第五篇 基于JSP 技术的网上购书系统——主页面和登录页面实现(网上商城、仿淘宝、当当、亚马逊)
目录 1.系统主界面 1.1功能说明 1.2界面设计 1.3处理流程 1.4 数据来源和算法 1.4.1数据来源 1.4.2查询条件 1.4.3表间关系 1.4.4相关sql实例 2.系统登陆后界面 2.1功能说明 2.2界面设计 2.3处理流程 2.4数据来源和算法 2.4.1数据来源 2.4.2查询条件 2.4.…...
【 云原生 | K8S 】kubeadm 部署Kubernetes集群
目录 1 环境准备 2 所有节点安装docker 3 所有节点安装kubeadm,kubelet和kubectl 4 部署K8S集群 4.1 查看初始化需要的镜像 4.2 初始化kubeadm 4.3 设定kubectl 4.4 所有节点部署网络插件flannel master(2C/4G,cpu核心数要求大于2&am…...
微信小程序rich-text 文本首行缩进和图片居中和富文本rich-text 解析多个空格不成功 nbsp
微信小程序开发使用rich-text组件渲染html格式的代码,常常因为不能自定义css导致文本不能缩进,以及图片不能居中等问题,这里可以考虑使用js的replace方法,替换字符串,然后在渲染的同时加载行内样式。 //获取字符串的图…...
DFRDisplayKm 实用指南:Apple Touch Bar Windows支持常见问题全解析
DFRDisplayKm 实用指南:Apple Touch Bar Windows支持常见问题全解析 【免费下载链接】DFRDisplayKm Windows infrastructure support for Apple DFR (Touch Bar) 项目地址: https://gitcode.com/gh_mirrors/df/DFRDisplayKm DFRDisplayKm 是一款专为 Windows…...
Apache Flink Agents 0.2.1 发布公告
Apache Flink 社区很高兴地宣布发布 Apache Flink Agents 0.2 系列的首个缺陷修复版本。 此版本包含 3 项缺陷和漏洞修复以及一些对Flink-Agents 0.2的小幅改进。下面列出了所有缺陷修复和改进内容(不包括构建基础设施和构建稳定性方面的改进)。如需查看…...
小白也能搞定:CYBER-VISION零号协议智能助盲系统部署全流程
小白也能搞定:CYBER-VISION零号协议智能助盲系统部署全流程 1. 系统介绍与准备工作 CYBER-VISION零号协议是一款专为视障人士设计的智能助盲系统,它通过先进的计算机视觉技术,将周围环境实时转化为可理解的语音提示。想象一下,当…...
Graphormer部署案例:中小企业AI药物研发团队低成本GPU算力部署方案
Graphormer部署案例:中小企业AI药物研发团队低成本GPU算力部署方案 1. 项目背景与价值 在药物研发领域,分子属性预测是核心环节之一。传统实验方法成本高昂且周期漫长,而Graphormer作为基于纯Transformer架构的图神经网络,为这一…...
音乐自由之路:Unlock-Music技术突破实战指南
音乐自由之路:Unlock-Music技术突破实战指南 【免费下载链接】unlock-music 在浏览器中解锁加密的音乐文件。原仓库: 1. https://github.com/unlock-music/unlock-music ;2. https://git.unlock-music.dev/um/web 项目地址: https://gitcod…...
Go AI 生态实战:从单机 RAG 到分布式智能服务架构演进
Go AI 生态实战:从单机 RAG 到分布式智能服务架构演进 摘要:本文面向具备后端与架构背景的技术人员,系统讲透 Go 在 AI 应用落地中的工程化方法。文章不再停留在“调用一个模型接口”的层面,而是从 RAG 原理、服务拆分、索引构建、高并发治理、缓存策略、容错机制、可观测性…...
Linux内核工程师面试高频问题解析
1. Linux内核工程师面试核心问题解析作为一名在Linux内核领域摸爬滚打多年的老手,我经历过无数次技术面试的洗礼。今天就把阿里云这类一线大厂在Linux内核工程师岗位上的高频面试题做个系统梳理,并附上我个人的解题思路和实战经验。这些题目看似基础&…...
AI辅助架构设计:让快马智能生成符合最佳实践的SpringBoot项目骨架
今天想和大家聊聊如何用AI工具快速搭建一个符合现代最佳实践的SpringBoot项目骨架。作为一个经常需要从零开始搭建项目的开发者,我发现传统的手动创建项目方式效率太低,而且容易遗漏一些关键配置。最近尝试了InsCode(快马)平台的AI辅助功能,发…...
吃透哈希槽:Redis集群核心分片机制,从原理到实战避坑
在分布式Redis集群中,“数据如何均匀分片、节点如何高效协同”是核心难题。上一篇我们详解了一致性哈希,它通过环形结构解决了传统哈希的节点迁移痛点,但在Redis集群的实际落地中,官方并没有采用一致性哈希,而是选择了…...
Simulink SVPWM模块输出对不上?别慌,可能是这两个参数没设对(附24V电机FOC仿真案例)
Simulink SVPWM模块输出差异排查指南:从参数配置到波形修正 引言 在电机控制系统的仿真与开发过程中,Simulink的SVPWM模块是工程师们常用的工具之一。然而,许多开发者在对比自带模块与自建模型输出时,经常会遇到令人困惑的波形不一…...
