当前位置: 首页 > news >正文

力扣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

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 前言一、力扣654. 最大二叉树二、力扣105. 从前序与中序遍历序列构造二叉树三、力扣106. 从中序与后序遍历序列构造二叉树四、力扣889. 根据前序和后序遍历构造二叉…...

Day01_《MySQL索引与性能优化》摘要

一、资料 视频&#xff1a;《尚硅谷MySQL数据库高级&#xff0c;mysql优化&#xff0c;数据库优化》—周阳 其他博主的完整笔记&#xff1a;MySQL 我的笔记&#xff1a;我的笔记只总结了视频p14-p46部分&#xff0c;因为只有这部分是讲解了MySQL的索引与explain语句分析优化…...

BMS系统项目

1、通过电压监测是否冲满&#xff0c;通过电压可以监测是否放完电 电池得参数 单体过压&#xff08;充满电&#xff09; 过压恢复&#xff08;百分之90多&#xff09; 欠压保护&#xff08;百分之几得电&#xff0c;快关机了&#xff09; 欠压恢复&#xff08;就是欠压之上…...

sql server 多行数据合并一行显示

在 SQL Server 中&#xff0c;可以使用 STUFF 和 FOR XML PATH 进行多行合并成一行。例如&#xff0c;假设有一个表名为 orders &#xff0c;其中包含订单号和产品名称&#xff1a; order_idproduct_name1Product A1Product B2Product C2Product D 以下查询将在 order_id 列上…...

「我的AIGC咒语库:分享和AI对话交流的秘诀——如何利用Prompt和AI进行高效交流?」

文章目录 每日一句正能量前言基础介绍什么是Prompt?什么是 Prompt Engineering&#xff1f;为什么需要 Prompt Engineering&#xff1f;如何进行 Prompt Engineering&#xff1f;Prompt的基本原则Prompt的编写模式AI 可以帮助程序员做什么&#xff1f;技术知识总结拆解任务阅读…...

强国有我助力苔花绽放 | 爱心捐赠仪式在西安顺利举办

2023年11月2日&#xff0c;由中国儿童中心、全国少年儿童“双有”主题教育活动组委会、中华少年儿童慈善救助基金会强国有我项目主办&#xff0c;陕西省青少年宫协会、陕西省妇女儿童活动中心、陕西回归儿童救助中心承办的“苔花绽放”事实无人抚养儿童关爱计划捐赠仪式在陕西回…...

Flink SQL -- CheckPoint

1、开启CheckPoint checkpoint可以定时将flink任务的状态持久化到hdfs中&#xff0c;任务执行失败重启可以保证中间结果不丢失 # 修改flink配置文件 vim flink-conf.yaml# checkppint 间隔时间 execution.checkpointing.interval: 1min # 任务手动取消时保存checkpoint execu…...

Load-balanced-online-OJ-system 负载均衡的OJ系统项目

前言 那么这里博主先安利一些干货满满的专栏了&#xff01; 首先是博主的高质量博客的汇总&#xff0c;这个专栏里面的博客&#xff0c;都是博主最最用心写的一部分&#xff0c;干货满满&#xff0c;希望对大家有帮助。 高质量博客汇总 本项目Github地址 - Load-balanced-o…...

ES6 导入导出

ES6 导入导出 ES6引入了原生的模块化支持&#xff0c;使得JavaScript代码可以被划分为可重用的模块。这些模块可以导出部分代码&#xff08;如函数、对象、类等&#xff09;&#xff0c;并被其他模块导入使用。 export 命名导出&#xff08;Named Exports&#xff09; 可以从…...

【Liunx】部署Ansible自动化运维工具

Ansible自动化运维工具 概述安装部署1.通过yum下载Ansible2.对自己做免密配置3.修改ansiable host配置对服务器进行分组4.测试&#xff1a;对所有服务器进行ping命令5.写playbook6.执行我们写的playbook脚本7.验证 概述 ansible是新出现的自动化运维工具&#xff0c;基于Pytho…...

Python的基础语法

1. 注释&#xff1a;在Python中&#xff0c;使用井号&#xff08;#&#xff09;表示单行注释&#xff0c;三个单引号&#xff08;&#xff09;或三个双引号&#xff08;"""&#xff09;表示多行注释。 2. 变量&#xff1a;在Python中&#xff0c;不需要声明变量…...

Skywalking流程分析_8(拦截器插件的加载)

前言 在之前的文章中我们将&#xff0c;静态方法、构造方法、实例方法的增强逻辑都分析完毕&#xff0c;但在增强前&#xff0c;对于拦截类的加载是至关重要的&#xff0c;下面我们就来详细的分析 增强插件的加载 静态方法增强前的加载 //clazz 要修改的字节码的原生类 Sta…...

智能AI系统ChatGPT网站源码+支持OpenAI DALL-E3文生图+支持ai绘画(Midjourney)/支持GPT全模型+国内AI全模型

一、AI创作系统 SparkAi创作系统是基于OpenAI很火的ChatGPT进行开发的Ai智能问答系统和Midjourney绘画系统&#xff0c;支持OpenAI-GPT全模型国内AI全模型。本期针对源码系统整体测试下来非常完美&#xff0c;可以说SparkAi是目前国内一款的ChatGPT对接OpenAI软件系统。那么如…...

腾讯云服务器可用区是什么意思?可用区选择方法

腾讯云服务器可用区是什么意思&#xff1f;云服务器可用区如何选择&#xff1f;可用区是指在同一个地域内电力和网络相互独立的区域&#xff0c;可用区可以做到故障隔离&#xff0c;所以可用区存在的意义在于构建高可用、高容灾应用&#xff0c;将应用部署在不同可用区内&#…...

Jupyter运行显存爆炸,明明上一个单元格已经运行完毕为什么还是会炸?

问题再现 上一个单元格运行完了train()&#xff0c;我想要用模型输出做点东西&#xff0c;可是提醒我显存不够&#xff1b; 在命令行中查看显存占用情况&#xff0c;发现4张卡都占满了&#xff0c;可真是太厉害了&#xff01; 解决方案 查看原来写的validate()&#xff0c;发…...

【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供应平台&#xff1a;聚合数据、百度APIStore、Apix、数说聚合、通联数据、HaoService、datasift 。排名不分先后&#xff01; 免费实用的API接口 第一部分 1、电商数据&#xff08;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&#xff0c;kubelet和kubectl 4 部署K8S集群 4.1 查看初始化需要的镜像 4.2 初始化kubeadm 4.3 设定kubectl 4.4 所有节点部署网络插件flannel master&#xff08;2C/4G&#xff0c;cpu核心数要求大于2&am…...

微信小程序rich-text 文本首行缩进和图片居中和富文本rich-text 解析多个空格不成功 nbsp

微信小程序开发使用rich-text组件渲染html格式的代码&#xff0c;常常因为不能自定义css导致文本不能缩进&#xff0c;以及图片不能居中等问题&#xff0c;这里可以考虑使用js的replace方法&#xff0c;替换字符串&#xff0c;然后在渲染的同时加载行内样式。 //获取字符串的图…...

多云管理“拦路虎”:深入解析网络互联、身份同步与成本可视化的技术复杂度​

一、引言&#xff1a;多云环境的技术复杂性本质​​ 企业采用多云策略已从技术选型升维至生存刚需。当业务系统分散部署在多个云平台时&#xff0c;​​基础设施的技术债呈现指数级积累​​。网络连接、身份认证、成本管理这三大核心挑战相互嵌套&#xff1a;跨云网络构建数据…...

conda相比python好处

Conda 作为 Python 的环境和包管理工具&#xff0c;相比原生 Python 生态&#xff08;如 pip 虚拟环境&#xff09;有许多独特优势&#xff0c;尤其在多项目管理、依赖处理和跨平台兼容性等方面表现更优。以下是 Conda 的核心好处&#xff1a; 一、一站式环境管理&#xff1a…...

shell脚本--常见案例

1、自动备份文件或目录 2、批量重命名文件 3、查找并删除指定名称的文件&#xff1a; 4、批量删除文件 5、查找并替换文件内容 6、批量创建文件 7、创建文件夹并移动文件 8、在文件夹中查找文件...

PPT|230页| 制造集团企业供应链端到端的数字化解决方案:从需求到结算的全链路业务闭环构建

制造业采购供应链管理是企业运营的核心环节&#xff0c;供应链协同管理在供应链上下游企业之间建立紧密的合作关系&#xff0c;通过信息共享、资源整合、业务协同等方式&#xff0c;实现供应链的全面管理和优化&#xff0c;提高供应链的效率和透明度&#xff0c;降低供应链的成…...

基于Uniapp开发HarmonyOS 5.0旅游应用技术实践

一、技术选型背景 1.跨平台优势 Uniapp采用Vue.js框架&#xff0c;支持"一次开发&#xff0c;多端部署"&#xff0c;可同步生成HarmonyOS、iOS、Android等多平台应用。 2.鸿蒙特性融合 HarmonyOS 5.0的分布式能力与原子化服务&#xff0c;为旅游应用带来&#xf…...

《用户共鸣指数(E)驱动品牌大模型种草:如何抢占大模型搜索结果情感高地》

在注意力分散、内容高度同质化的时代&#xff0c;情感连接已成为品牌破圈的关键通道。我们在服务大量品牌客户的过程中发现&#xff0c;消费者对内容的“有感”程度&#xff0c;正日益成为影响品牌传播效率与转化率的核心变量。在生成式AI驱动的内容生成与推荐环境中&#xff0…...

在 Nginx Stream 层“改写”MQTT ngx_stream_mqtt_filter_module

1、为什么要修改 CONNECT 报文&#xff1f; 多租户隔离&#xff1a;自动为接入设备追加租户前缀&#xff0c;后端按 ClientID 拆分队列。零代码鉴权&#xff1a;将入站用户名替换为 OAuth Access-Token&#xff0c;后端 Broker 统一校验。灰度发布&#xff1a;根据 IP/地理位写…...

将对透视变换后的图像使用Otsu进行阈值化,来分离黑色和白色像素。这句话中的Otsu是什么意思?

Otsu 是一种自动阈值化方法&#xff0c;用于将图像分割为前景和背景。它通过最小化图像的类内方差或等价地最大化类间方差来选择最佳阈值。这种方法特别适用于图像的二值化处理&#xff0c;能够自动确定一个阈值&#xff0c;将图像中的像素分为黑色和白色两类。 Otsu 方法的原…...

3403. 从盒子中找出字典序最大的字符串 I

3403. 从盒子中找出字典序最大的字符串 I 题目链接&#xff1a;3403. 从盒子中找出字典序最大的字符串 I 代码如下&#xff1a; class Solution { public:string answerString(string word, int numFriends) {if (numFriends 1) {return word;}string res;for (int i 0;i &…...

Angular微前端架构:Module Federation + ngx-build-plus (Webpack)

以下是一个完整的 Angular 微前端示例&#xff0c;其中使用的是 Module Federation 和 npx-build-plus 实现了主应用&#xff08;Shell&#xff09;与子应用&#xff08;Remote&#xff09;的集成。 &#x1f6e0;️ 项目结构 angular-mf/ ├── shell-app/ # 主应用&…...