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

脑机新手指南(八):OpenBCI_GUI:从环境搭建到数据可视化(下)

一、数据处理与分析实战 &#xff08;一&#xff09;实时滤波与参数调整 基础滤波操作 60Hz 工频滤波&#xff1a;勾选界面右侧 “60Hz” 复选框&#xff0c;可有效抑制电网干扰&#xff08;适用于北美地区&#xff0c;欧洲用户可调整为 50Hz&#xff09;。 平滑处理&…...

基于距离变化能量开销动态调整的WSN低功耗拓扑控制开销算法matlab仿真

目录 1.程序功能描述 2.测试软件版本以及运行结果展示 3.核心程序 4.算法仿真参数 5.算法理论概述 6.参考文献 7.完整程序 1.程序功能描述 通过动态调整节点通信的能量开销&#xff0c;平衡网络负载&#xff0c;延长WSN生命周期。具体通过建立基于距离的能量消耗模型&am…...

循环冗余码校验CRC码 算法步骤+详细实例计算

通信过程&#xff1a;&#xff08;白话解释&#xff09; 我们将原始待发送的消息称为 M M M&#xff0c;依据发送接收消息双方约定的生成多项式 G ( x ) G(x) G(x)&#xff08;意思就是 G &#xff08; x ) G&#xff08;x) G&#xff08;x) 是已知的&#xff09;&#xff0…...

线程同步:确保多线程程序的安全与高效!

全文目录&#xff1a; 开篇语前序前言第一部分&#xff1a;线程同步的概念与问题1.1 线程同步的概念1.2 线程同步的问题1.3 线程同步的解决方案 第二部分&#xff1a;synchronized关键字的使用2.1 使用 synchronized修饰方法2.2 使用 synchronized修饰代码块 第三部分&#xff…...

抖音增长新引擎:品融电商,一站式全案代运营领跑者

抖音增长新引擎&#xff1a;品融电商&#xff0c;一站式全案代运营领跑者 在抖音这个日活超7亿的流量汪洋中&#xff0c;品牌如何破浪前行&#xff1f;自建团队成本高、效果难控&#xff1b;碎片化运营又难成合力——这正是许多企业面临的增长困局。品融电商以「抖音全案代运营…...

全球首个30米分辨率湿地数据集(2000—2022)

数据简介 今天我们分享的数据是全球30米分辨率湿地数据集&#xff0c;包含8种湿地亚类&#xff0c;该数据以0.5X0.5的瓦片存储&#xff0c;我们整理了所有属于中国的瓦片名称与其对应省份&#xff0c;方便大家研究使用。 该数据集作为全球首个30米分辨率、覆盖2000–2022年时间…...

c++ 面试题(1)-----深度优先搜索(DFS)实现

操作系统&#xff1a;ubuntu22.04 IDE:Visual Studio Code 编程语言&#xff1a;C11 题目描述 地上有一个 m 行 n 列的方格&#xff0c;从坐标 [0,0] 起始。一个机器人可以从某一格移动到上下左右四个格子&#xff0c;但不能进入行坐标和列坐标的数位之和大于 k 的格子。 例…...

Frozen-Flask :将 Flask 应用“冻结”为静态文件

Frozen-Flask 是一个用于将 Flask 应用“冻结”为静态文件的 Python 扩展。它的核心用途是&#xff1a;将一个 Flask Web 应用生成成纯静态 HTML 文件&#xff0c;从而可以部署到静态网站托管服务上&#xff0c;如 GitHub Pages、Netlify 或任何支持静态文件的网站服务器。 &am…...

12.找到字符串中所有字母异位词

&#x1f9e0; 题目解析 题目描述&#xff1a; 给定两个字符串 s 和 p&#xff0c;找出 s 中所有 p 的字母异位词的起始索引。 返回的答案以数组形式表示。 字母异位词定义&#xff1a; 若两个字符串包含的字符种类和出现次数完全相同&#xff0c;顺序无所谓&#xff0c;则互为…...

SpringCloudGateway 自定义局部过滤器

场景&#xff1a; 将所有请求转化为同一路径请求&#xff08;方便穿网配置&#xff09;在请求头内标识原来路径&#xff0c;然后在将请求分发给不同服务 AllToOneGatewayFilterFactory import lombok.Getter; import lombok.Setter; import lombok.extern.slf4j.Slf4j; impor…...