当前位置: 首页 > 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;然后在渲染的同时加载行内样式。 //获取字符串的图…...

企业级OA系统高可用方案:泛微ecology+Nginx负载均衡最佳实践

企业级OA系统高可用架构设计与实践&#xff1a;泛微ecologyNginxResin全栈解决方案 在数字化转型浪潮中&#xff0c;办公自动化系统(OA)已成为企业核心IT基础设施。作为国内领先的协同管理平台&#xff0c;泛微ecology承载着企业关键业务流程&#xff0c;其稳定性直接影响组织运…...

Qwen3-Embedding-4B应用分享:打造智能法律合同检索系统,快速找到关键条款

Qwen3-Embedding-4B应用分享&#xff1a;打造智能法律合同检索系统&#xff0c;快速找到关键条款 1. 引言&#xff1a;法律合同检索的痛点与解决方案 在法律实务工作中&#xff0c;合同审查是一项耗时且关键的任务。律师和法务人员经常需要从数百页的合同中快速定位特定条款&…...

新手入门指南:在快马平台用AI生成代码理解云桌面基础概念

今天想和大家分享一个特别适合新手理解云桌面基础概念的实践方法。作为一个刚接触云计算的小白&#xff0c;我最初对"一台主机创建多个云桌面"这个概念也是一头雾水&#xff0c;直到在InsCode(快马)平台上尝试用AI生成代码来模拟这个过程&#xff0c;才真正搞明白其中…...

Jimeng LoRA效果对比:同一seed下不同Epoch生成图随机性与稳定性分析

Jimeng LoRA效果对比&#xff1a;同一seed下不同Epoch生成图随机性与稳定性分析 1. 项目简介&#xff1a;一个专为LoRA效果测试而生的工具 如果你玩过Stable Diffusion&#xff0c;肯定对LoRA不陌生。它是一种轻量化的模型微调方法&#xff0c;能在不改变基础大模型的情况下&…...

MaxKB社区版限制解除后,别忘了检查这3个地方!v1.10.2-lts实战经验分享

MaxKB社区版限制解除后的深度验证指南&#xff1a;v1.10.2-lts实战经验 当你按照教程完成MaxKB社区版的限制解除操作后&#xff0c;真正的挑战才刚刚开始。很多技术人员在修改代码并重启服务后&#xff0c;往往以为大功告成&#xff0c;却忽略了后续的关键验证步骤。本文将带你…...

iptables实战指南:从链表关系到规则配置的完整解析

1. iptables基础概念与核心组件 第一次接触iptables时&#xff0c;我盯着那些复杂的规则配置看了整整一个下午。后来才发现&#xff0c;理解iptables的关键在于掌握它的"四表五链"架构。简单来说&#xff0c;iptables就像是一个多层安检系统&#xff0c;数据包要经过…...

PyTorch张量操作实战:从基础运算到CNN应用

1. PyTorch张量基础&#xff1a;从概念到创建 第一次接触PyTorch张量时&#xff0c;我完全被各种术语搞晕了。什么标量、向量、矩阵&#xff0c;还有这个奇怪的"张量"词。后来才发现&#xff0c;其实张量就是多维数组的另一种说法&#xff0c;只不过在深度学习中我们…...

GyverDS18库:工业级DS18B20单总线温度驱动设计与实践

1. GyverDS18库深度解析&#xff1a;面向工业级应用的DS18B20全功能驱动设计Dallas DS18B20是业界最成熟的单总线数字温度传感器之一&#xff0c;凭借其独特的1-Wire协议、无需外部ADC、支持多点组网及寄生供电能力&#xff0c;在工业监控、环境监测、智能家电等领域广泛应用。…...

Tetrazine-amine HCl salt,CAS:1416711-59-5,四嗪-氨基盐酸盐的描述

Tetrazine-amine HCl salt&#xff08;四嗪-氨基盐酸盐&#xff09;是一种结合了四嗪基团和氨基盐酸盐结构的化合物&#xff0c;在化学、生物医药和材料科学等领域具有广泛应用。一、基本信息中文名称&#xff1a;四嗪-氨基盐酸盐英文名称&#xff1a;Tetrazine-amine HCl salt…...

3步革新Windows任务栏:TranslucentTB打造个性化桌面体验

3步革新Windows任务栏&#xff1a;TranslucentTB打造个性化桌面体验 【免费下载链接】TranslucentTB A lightweight utility that makes the Windows taskbar translucent/transparent. 项目地址: https://gitcode.com/gh_mirrors/tr/TranslucentTB 在视觉主导的数字时代…...