力扣爆刷第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的位置,记录初始和最后的位置 找出所有合法日期的位置,使用前缀和,计…...
7.4.分块查找
一.分块查找的算法思想: 1.实例: 以上述图片的顺序表为例, 该顺序表的数据元素从整体来看是乱序的,但如果把这些数据元素分成一块一块的小区间, 第一个区间[0,1]索引上的数据元素都是小于等于10的, 第二…...
如何将联系人从 iPhone 转移到 Android
从 iPhone 换到 Android 手机时,你可能需要保留重要的数据,例如通讯录。好在,将通讯录从 iPhone 转移到 Android 手机非常简单,你可以从本文中学习 6 种可靠的方法,确保随时保持连接,不错过任何信息。 第 1…...
C++.OpenGL (10/64)基础光照(Basic Lighting)
基础光照(Basic Lighting) 冯氏光照模型(Phong Lighting Model) #mermaid-svg-GLdskXwWINxNGHso {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-GLdskXwWINxNGHso .error-icon{fill:#552222;}#mermaid-svg-GLd…...
C++ 求圆面积的程序(Program to find area of a circle)
给定半径r,求圆的面积。圆的面积应精确到小数点后5位。 例子: 输入:r 5 输出:78.53982 解释:由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982,因为我们只保留小数点后 5 位数字。 输…...
pikachu靶场通关笔记22-1 SQL注入05-1-insert注入(报错法)
目录 一、SQL注入 二、insert注入 三、报错型注入 四、updatexml函数 五、源码审计 六、insert渗透实战 1、渗透准备 2、获取数据库名database 3、获取表名table 4、获取列名column 5、获取字段 本系列为通过《pikachu靶场通关笔记》的SQL注入关卡(共10关࿰…...
Java线上CPU飙高问题排查全指南
一、引言 在Java应用的线上运行环境中,CPU飙高是一个常见且棘手的性能问题。当系统出现CPU飙高时,通常会导致应用响应缓慢,甚至服务不可用,严重影响用户体验和业务运行。因此,掌握一套科学有效的CPU飙高问题排查方法&…...
用机器学习破解新能源领域的“弃风”难题
音乐发烧友深有体会,玩音乐的本质就是玩电网。火电声音偏暖,水电偏冷,风电偏空旷。至于太阳能发的电,则略显朦胧和单薄。 不知你是否有感觉,近两年家里的音响声音越来越冷,听起来越来越单薄? —…...
实战三:开发网页端界面完成黑白视频转为彩色视频
一、需求描述 设计一个简单的视频上色应用,用户可以通过网页界面上传黑白视频,系统会自动将其转换为彩色视频。整个过程对用户来说非常简单直观,不需要了解技术细节。 效果图 二、实现思路 总体思路: 用户通过Gradio界面上…...
xmind转换为markdown
文章目录 解锁思维导图新姿势:将XMind转为结构化Markdown 一、认识Xmind结构二、核心转换流程详解1.解压XMind文件(ZIP处理)2.解析JSON数据结构3:递归转换树形结构4:Markdown层级生成逻辑 三、完整代码 解锁思维导图新…...
篇章二 论坛系统——系统设计
目录 2.系统设计 2.1 技术选型 2.2 设计数据库结构 2.2.1 数据库实体 1. 数据库设计 1.1 数据库名: forum db 1.2 表的设计 1.3 编写SQL 2.系统设计 2.1 技术选型 2.2 设计数据库结构 2.2.1 数据库实体 通过需求分析获得概念类并结合业务实现过程中的技术需要&#x…...
