力扣爆刷第142天之二叉树五连刷(构造树、搜索树)
力扣爆刷第142天之二叉树五连刷(构造树、搜索树)
文章目录
- 力扣爆刷第142天之二叉树五连刷(构造树、搜索树)
- 一、106. 从中序与后序遍历序列构造二叉树
- 二、654. 最大二叉树
- 三、617. 合并二叉树
- 四、700. 二叉搜索树中的搜索
- 五、98. 验证二叉搜索树
一、106. 从中序与后序遍历序列构造二叉树
题目链接:https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/description/
思路:首先把中序遍历的key和value用map记录下来,节省通过后序定位根节点的时间,然后不断的用父节点划分左右子数组。
class Solution {Map<Integer, Integer> map = new HashMap<>();public TreeNode buildTree(int[] inorder, int[] postorder) {for(int i = 0; i < inorder.length; i++) {map.put(inorder[i], i);}return traverse(inorder, postorder, 0, inorder.length-1, 0, postorder.length-1);}TreeNode traverse(int[] inorder, int[] postorder, int leftIn, int rightIn, int leftPo, int rightPo) {if(leftIn > rightIn) return null;int mid = map.get(postorder[rightPo]);TreeNode root = new TreeNode(postorder[rightPo]);root.left = traverse(inorder, postorder, leftIn, mid-1, leftPo, leftPo+mid-leftIn-1);root.right = traverse(inorder, postorder, mid+1, rightIn, leftPo+mid-leftIn, rightPo-1);return root;}}
二、654. 最大二叉树
题目链接:https://leetcode.cn/problems/maximum-binary-tree/description/
思路:也是前序遍历构建二叉树,在每一次指定区间的内,通过比较获取最大值,然后通过最大值划分左右子数组。
class Solution {public TreeNode constructMaximumBinaryTree(int[] nums) {return buildTree(nums, 0, nums.length-1);}TreeNode buildTree(int[] nums, int left, int right) {if(left > right) return null;int max = nums[left], mid = left;for(int i = left; i <= right; i++) {if(nums[i] > max) {max = nums[i];mid = i;}}TreeNode root = new TreeNode(max);root.left = buildTree(nums, left, mid-1);root.right = buildTree(nums, mid+1, right);return root;}
}
三、617. 合并二叉树
题目链接:https://leetcode.cn/problems/merge-two-binary-trees/description/
思路:合并二叉树,其实就是遍历其中一棵树,然后把另外一颗树连接到这棵树上。
class Solution {public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {if(root1 == null && root2 == null) {return null;}if(root1 == null) return root2;if(root2 == null) return root1;root1.val += root2.val;root1.left = mergeTrees(root1.left, root2.left);root1.right = mergeTrees(root1.right, root2.right);return root1;}}
四、700. 二叉搜索树中的搜索
题目链接:https://leetcode.cn/problems/search-in-a-binary-search-tree/description/
思路:利用二叉搜索树的特性,从上往下进行搜索,相等返回,小于去左子树,大于去右子树。
class Solution {public TreeNode searchBST(TreeNode root, int val) {if(root == null) return null;if(root.val == val) {return root;}else if(root.val > val) {return searchBST(root.left, val);}else{return searchBST(root.right, val);}}}
五、98. 验证二叉搜索树
题目链接:https://leetcode.cn/problems/validate-binary-search-tree/description/
思路:要想验证是不是二叉搜索树,直接利用二叉搜索树的特性,中序单调遍历递增,只要非单调递增即不是。
class Solution {boolean flag = true;TreeNode p = null;public boolean isValidBST(TreeNode root) {traverse(root);return flag;}void traverse(TreeNode root) {if(root == null) return ;traverse(root.left);if(p != null) {if(p.val >= root.val) {flag = false;return ;}}p = root;traverse(root.right);}
}
相关文章:
力扣爆刷第142天之二叉树五连刷(构造树、搜索树)
力扣爆刷第142天之二叉树五连刷(构造树、搜索树) 文章目录 力扣爆刷第142天之二叉树五连刷(构造树、搜索树)一、106. 从中序与后序遍历序列构造二叉树二、654. 最大二叉树三、617. 合并二叉树四、700. 二叉搜索树中的搜索五、98. …...
0407放大电路的频率响应
放大电路的频率响应 单时间常数RC电路的频率响应中频响应高频响应低频响应全频域响应 放大电路频率响应概述1. 直接耦合放大电路频域响应阻容耦合放大电路频域响应 4.7.1 单时间常数RC电路的频率响应 4.7.2 放大电路频率响应概述 4.7.3 单级共射极放大电路的频率响应 4.7.4 单级…...
数据分析必备:一步步教你如何用Pandas做数据分析(6)
1、Pandas 函数应用 Pandas 重建索引操作实例 要将您自己或其他库的函数应用于Pandas对象,您应该了解三个重要的方法。方法如下所述。要使用的适当方法取决于您的函数是希望对整个数据帧进行操作,还是行操作还是按列操作,还是按元素操作。 表…...
Spring Cloud系列—Spring Cloud Gateway服务网关的部署与使用指南
Gateway网关 文章目录 Gateway网关1. 网关基本简介1.1 什么是网关1.2 为什么需要网关? 2. 快速搭建gateway网关2.1 创建新模块2.2 引入依赖2.3 编写启动类2.4 配置路由规则2.5 测试 3. 路由过滤4. 过滤器4.1 简介4.2 网关过滤器4.2.2 种类 4.3 自定义过滤器4.3.1 自…...
创建一个python的Django项目文件
创建一个python的Django项目文件(内含conda) 文章目录 创建一个python的Django项目文件(内含conda)前言一、conda环境的下载二、配置conda的环境变量三、激活管理环境四、下载Django五、创建Django项目文件六、启动Django文件七、用pycharm直接创建Django文件 前言 大家好,今天…...
NB49 牛群的秘密通信
描述 在一个远离人类的世界中,有一群牛正在进行秘密通信。它们使用一种特殊的括号组合作为加密通信的形式。每一组加密信息均包括以下字符:(,{,[,),},]。 加密信息需要满足以下有效性规则: 每个左括号必须使用相同类型的右括号闭合。左括号…...
Git系列:git mv 高效的文件重命名与移动操作
💝💝💝欢迎莅临我的博客,很高兴能够在这里和您见面!希望您在这里可以感受到一份轻松愉快的氛围,不仅可以获得有趣的内容和知识,也可以畅所欲言、分享您的想法和见解。 推荐:「stormsha的主页」…...
美区TikTok小店又出潜力爆品!“痘痘贴”一周销售八万单!
保健品在美区小店“大杀四方”的同时,个别美妆个护单品也在悄悄上分。 据超店有数的「销量飙升榜」显示,一款由Zikoo推出的“痘痘贴”最近一周内销量正在飞速上升,环比增长高达209.29%,销量近8万件。 来源:超店有数「销…...
C++两种内置栈的使用
第一种:使用C内置栈数据类型 stack<int> q; //C内置栈数据类型 int x; q.push(x); //将x压入栈顶 q.top(); //返回栈顶的元素 q.pop(); //删除栈顶的元素 q.size(); //返回栈中元素的个数 q.empty(); //检查栈是否为空,若为空返回true,否则返回false第二…...
如何用电脑批量操作多部手机
如果你有很多手机,然后需要在这些手机上同时执行相同的操作,这个时候如果能有一种办法批量操作,将会大大提高效率,节省很多时间。本文将介绍基于uiautomator2实现的群控手机方案。 uiautomator2 是 一种 Android 自动化测试框架&…...
Delphi 程序例子(DPI变化自动感知及显示器相关功能演示)
目录 一、前言 二、Delphi 演示程序(D12版本,用D11也都可以) 1. 演示程序功能: 2. 程序界面: 3. 程序源代码下载(有偿): 一、前言 系列文章: 彻底搞懂 Windows 显示…...
mysql主从复制的步骤和使用到的操作命令有哪些?
步骤: 配置主服务器(Master): 启用二进制日志记录(binary logging)。配置主服务器的唯一标识(server-id)。创建用于复制的专用复制账户。 配置从服务器(Slave࿰…...
[AIGC] Java CompletableFuture:简介及示例
Java 8 引入了一个名为 CompletableFuture 的新库,正如其名称所示,该库提供了一种名为 “Completable Future” 的新 API,其主要目的是支持异步编程,并通过可搜索的操作将这些异步操作进行聚合管控。 文章目录 CompletableFuture …...
五步定位性能瓶颈
一、着手测试前的准备:优化数据流向与系统架构分析 在进行性能测试或系统优化之前,明确数据流向和系统架构的细节是至关重要的步骤。这不仅能够帮助识别潜在的瓶颈,还能确保测试用例设计的全面性与针对性。以下是关键步骤和方法:…...
currentTarget指向监听者Target:指向触发者
在JavaScript的事件处理中,currentTarget 和 target 是两个重要的属性,它们常常用于区分事件处理函数当前绑定的元素和实际触发事件的元素。这两个属性的意义可以用下面的方式解释: currentTarget 指向监听者:这意味着currentTa…...
OpenAI宫斗剧番外篇: “Ilya与Altman联手对抗微软大帝,扫除黑恶势力”,“余华”和“莫言”犀利点评
事情是这样的。 小编我是一个重度的智谱清言用户,最近智谱清言悄悄上线了一个“划词引用”功能后,我仿佛打开了新世界的大门。我甚至用这个小功能,玩出来了即将为你上映的《OpenAI宫斗剧番外篇》。 3.5研究测试:hujiaoai.cn 4研…...
网关路由SpringCloudGateway、nacos配置管理(热更新、动态路由)
文章目录 前言一、网关路由二、SpringCloudGateway1. 路由过滤2. 网关登录校验2.1 鉴权2.2 网关过滤器2.3 登录校验2.3.1 JWT2.3.2 登录校验过滤器 3. 微服务从网关获取用户4. 微服务之间用户信息传递 三、nacos配置管理问题引入3.1 配置共享3.1.1 在Nacos中添加共享配置3.1.2 …...
关于linux的防护,以及群集你要知道的有哪些11-搭建Zabbix监控系统
1、zabbix具备功能 主机的性能监控、网络设备性能监控、数据库性能监控、多种警告方式、详细报表图表绘制 2、zabbix的监测对象 Linux服务器、Windows服务器、路由器、交换机等网络设备 3、zabbix的监控架构 server-client架构:适用于网络比较简单,…...
腾讯云环境安装单机版minio
Minio 下载安装 wget https://dl.min.io/server/minio/release/linux-amd64/minio修改minio 文件为可执行文件 chmod x minio3、启动,随机端口启动 ./minio server /data/miniodata # 或者指定密码执行 MINIO_ACCESS_KEYmyminioadmin MINIO_SECRET_KEYmyminioadm…...
蓝桥杯2023(十四届)省赛——统计日期(八重神子)
统计日期 2.日期统计 - 蓝桥云课 (lanqiao.cn) 其实一开始我想直接暴力的,然后写着写着突然觉得可以优化一下: 优化方法:先找所有2023的位置,记录初始和最后的位置 找出所有合法日期的位置,使用前缀和,计…...
KubeSphere 容器平台高可用:环境搭建与可视化操作指南
Linux_k8s篇 欢迎来到Linux的世界,看笔记好好学多敲多打,每个人都是大神! 题目:KubeSphere 容器平台高可用:环境搭建与可视化操作指南 版本号: 1.0,0 作者: 老王要学习 日期: 2025.06.05 适用环境: Ubuntu22 文档说…...
XCTF-web-easyupload
试了试php,php7,pht,phtml等,都没有用 尝试.user.ini 抓包修改将.user.ini修改为jpg图片 在上传一个123.jpg 用蚁剑连接,得到flag...
2025年能源电力系统与流体力学国际会议 (EPSFD 2025)
2025年能源电力系统与流体力学国际会议(EPSFD 2025)将于本年度在美丽的杭州盛大召开。作为全球能源、电力系统以及流体力学领域的顶级盛会,EPSFD 2025旨在为来自世界各地的科学家、工程师和研究人员提供一个展示最新研究成果、分享实践经验及…...
2025 后端自学UNIAPP【项目实战:旅游项目】6、我的收藏页面
代码框架视图 1、先添加一个获取收藏景点的列表请求 【在文件my_api.js文件中添加】 // 引入公共的请求封装 import http from ./my_http.js// 登录接口(适配服务端返回 Token) export const login async (code, avatar) > {const res await http…...
从零开始打造 OpenSTLinux 6.6 Yocto 系统(基于STM32CubeMX)(九)
设备树移植 和uboot设备树修改的内容同步到kernel将设备树stm32mp157d-stm32mp157daa1-mx.dts复制到内核源码目录下 源码修改及编译 修改arch/arm/boot/dts/st/Makefile,新增设备树编译 stm32mp157f-ev1-m4-examples.dtb \stm32mp157d-stm32mp157daa1-mx.dtb修改…...
汇编常见指令
汇编常见指令 一、数据传送指令 指令功能示例说明MOV数据传送MOV EAX, 10将立即数 10 送入 EAXMOV [EBX], EAX将 EAX 值存入 EBX 指向的内存LEA加载有效地址LEA EAX, [EBX4]将 EBX4 的地址存入 EAX(不访问内存)XCHG交换数据XCHG EAX, EBX交换 EAX 和 EB…...
智能仓储的未来:自动化、AI与数据分析如何重塑物流中心
当仓库学会“思考”,物流的终极形态正在诞生 想象这样的场景: 凌晨3点,某物流中心灯火通明却空无一人。AGV机器人集群根据实时订单动态规划路径;AI视觉系统在0.1秒内扫描包裹信息;数字孪生平台正模拟次日峰值流量压力…...
Spring数据访问模块设计
前面我们已经完成了IoC和web模块的设计,聪明的码友立马就知道了,该到数据访问模块了,要不就这俩玩个6啊,查库势在必行,至此,它来了。 一、核心设计理念 1、痛点在哪 应用离不开数据(数据库、No…...
Device Mapper 机制
Device Mapper 机制详解 Device Mapper(简称 DM)是 Linux 内核中的一套通用块设备映射框架,为 LVM、加密磁盘、RAID 等提供底层支持。本文将详细介绍 Device Mapper 的原理、实现、内核配置、常用工具、操作测试流程,并配以详细的…...
Typeerror: cannot read properties of undefined (reading ‘XXX‘)
最近需要在离线机器上运行软件,所以得把软件用docker打包起来,大部分功能都没问题,出了一个奇怪的事情。同样的代码,在本机上用vscode可以运行起来,但是打包之后在docker里出现了问题。使用的是dialog组件,…...
