力扣爆刷第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的位置,记录初始和最后的位置 找出所有合法日期的位置,使用前缀和,计…...
在Ubuntu中设置开机自动运行(sudo)指令的指南
在Ubuntu系统中,有时需要在系统启动时自动执行某些命令,特别是需要 sudo权限的指令。为了实现这一功能,可以使用多种方法,包括编写Systemd服务、配置 rc.local文件或使用 cron任务计划。本文将详细介绍这些方法,并提供…...
微信小程序云开发平台MySQL的连接方式
注:微信小程序云开发平台指的是腾讯云开发 先给结论:微信小程序云开发平台的MySQL,无法通过获取数据库连接信息的方式进行连接,连接只能通过云开发的SDK连接,具体要参考官方文档: 为什么? 因为…...
Unit 1 深度强化学习简介
Deep RL Course ——Unit 1 Introduction 从理论和实践层面深入学习深度强化学习。学会使用知名的深度强化学习库,例如 Stable Baselines3、RL Baselines3 Zoo、Sample Factory 和 CleanRL。在独特的环境中训练智能体,比如 SnowballFight、Huggy the Do…...
Map相关知识
数据结构 二叉树 二叉树,顾名思义,每个节点最多有两个“叉”,也就是两个子节点,分别是左子 节点和右子节点。不过,二叉树并不要求每个节点都有两个子节点,有的节点只 有左子节点,有的节点只有…...
深度学习习题2
1.如果增加神经网络的宽度,精确度会增加到一个特定阈值后,便开始降低。造成这一现象的可能原因是什么? A、即使增加卷积核的数量,只有少部分的核会被用作预测 B、当卷积核数量增加时,神经网络的预测能力会降低 C、当卷…...
LLMs 系列实操科普(1)
写在前面: 本期内容我们继续 Andrej Karpathy 的《How I use LLMs》讲座内容,原视频时长 ~130 分钟,以实操演示主流的一些 LLMs 的使用,由于涉及到实操,实际上并不适合以文字整理,但还是决定尽量整理一份笔…...
逻辑回归暴力训练预测金融欺诈
简述 「使用逻辑回归暴力预测金融欺诈,并不断增加特征维度持续测试」的做法,体现了一种逐步建模与迭代验证的实验思路,在金融欺诈检测中非常有价值,本文作为一篇回顾性记录了早年间公司给某行做反欺诈预测用到的技术和思路。百度…...
适应性Java用于现代 API:REST、GraphQL 和事件驱动
在快速发展的软件开发领域,REST、GraphQL 和事件驱动架构等新的 API 标准对于构建可扩展、高效的系统至关重要。Java 在现代 API 方面以其在企业应用中的稳定性而闻名,不断适应这些现代范式的需求。随着不断发展的生态系统,Java 在现代 API 方…...
Linux部署私有文件管理系统MinIO
最近需要用到一个文件管理服务,但是又不想花钱,所以就想着自己搭建一个,刚好我们用的一个开源框架已经集成了MinIO,所以就选了这个 我这边对文件服务性能要求不是太高,单机版就可以 安装非常简单,几个命令就…...
Unity中的transform.up
2025年6月8日,周日下午 在Unity中,transform.up是Transform组件的一个属性,表示游戏对象在世界空间中的“上”方向(Y轴正方向),且会随对象旋转动态变化。以下是关键点解析: 基本定义 transfor…...
