力扣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方法,替换字符串,然后在渲染的同时加载行内样式。 //获取字符串的图…...

龙虎榜——20250610
上证指数放量收阴线,个股多数下跌,盘中受消息影响大幅波动。 深证指数放量收阴线形成顶分型,指数短线有调整的需求,大概需要一两天。 2025年6月10日龙虎榜行业方向分析 1. 金融科技 代表标的:御银股份、雄帝科技 驱动…...

C++初阶-list的底层
目录 1.std::list实现的所有代码 2.list的简单介绍 2.1实现list的类 2.2_list_iterator的实现 2.2.1_list_iterator实现的原因和好处 2.2.2_list_iterator实现 2.3_list_node的实现 2.3.1. 避免递归的模板依赖 2.3.2. 内存布局一致性 2.3.3. 类型安全的替代方案 2.3.…...
逻辑回归:给不确定性划界的分类大师
想象你是一名医生。面对患者的检查报告(肿瘤大小、血液指标),你需要做出一个**决定性判断**:恶性还是良性?这种“非黑即白”的抉择,正是**逻辑回归(Logistic Regression)** 的战场&a…...

Redis相关知识总结(缓存雪崩,缓存穿透,缓存击穿,Redis实现分布式锁,如何保持数据库和缓存一致)
文章目录 1.什么是Redis?2.为什么要使用redis作为mysql的缓存?3.什么是缓存雪崩、缓存穿透、缓存击穿?3.1缓存雪崩3.1.1 大量缓存同时过期3.1.2 Redis宕机 3.2 缓存击穿3.3 缓存穿透3.4 总结 4. 数据库和缓存如何保持一致性5. Redis实现分布式…...

YSYX学习记录(八)
C语言,练习0: 先创建一个文件夹,我用的是物理机: 安装build-essential 练习1: 我注释掉了 #include <stdio.h> 出现下面错误 在你的文本编辑器中打开ex1文件,随机修改或删除一部分,之后…...

STM32F4基本定时器使用和原理详解
STM32F4基本定时器使用和原理详解 前言如何确定定时器挂载在哪条时钟线上配置及使用方法参数配置PrescalerCounter ModeCounter Periodauto-reload preloadTrigger Event Selection 中断配置生成的代码及使用方法初始化代码基本定时器触发DCA或者ADC的代码讲解中断代码定时启动…...

《用户共鸣指数(E)驱动品牌大模型种草:如何抢占大模型搜索结果情感高地》
在注意力分散、内容高度同质化的时代,情感连接已成为品牌破圈的关键通道。我们在服务大量品牌客户的过程中发现,消费者对内容的“有感”程度,正日益成为影响品牌传播效率与转化率的核心变量。在生成式AI驱动的内容生成与推荐环境中࿰…...

04-初识css
一、css样式引入 1.1.内部样式 <div style"width: 100px;"></div>1.2.外部样式 1.2.1.外部样式1 <style>.aa {width: 100px;} </style> <div class"aa"></div>1.2.2.外部样式2 <!-- rel内表面引入的是style样…...
数据库分批入库
今天在工作中,遇到一个问题,就是分批查询的时候,由于批次过大导致出现了一些问题,一下是问题描述和解决方案: 示例: // 假设已有数据列表 dataList 和 PreparedStatement pstmt int batchSize 1000; // …...

Mac下Android Studio扫描根目录卡死问题记录
环境信息 操作系统: macOS 15.5 (Apple M2芯片)Android Studio版本: Meerkat Feature Drop | 2024.3.2 Patch 1 (Build #AI-243.26053.27.2432.13536105, 2025年5月22日构建) 问题现象 在项目开发过程中,提示一个依赖外部头文件的cpp源文件需要同步,点…...