当前位置: 首页 > news >正文

代码随想录算法训练营第23期day19| 654.最大二叉树、617.合并二叉树、700.二叉搜索树中的搜索、98.验证二叉搜索树

目录

一、(leetcode 654)最大二叉树

二、(leetcode 617)合并二叉树

三、(leetcode 700)二叉搜索树中的搜索

四、(leetcode 98)验证二叉搜索树


一、(leetcode 654)最大二叉树

力扣题目地址

状态:AC。

和昨天的中序+后/前序遍历序列构建二叉树思路类似,每次递归寻找数组中的最大值,根据最大值的索引来切分左右子序列进行递归生成,可以用索引下标来避免重复生成vector带来的开销

class Solution {
public:TreeNode* traversal(vector<int>& nums, int begin, int end){if(begin == end) { return nullptr; }int max_num = INT_MIN, max_index = begin;// 确定最大值的索引for(int i = begin; i < end; ++i){if(max_num < nums[i]){max_num = nums[i];max_index = i;}}TreeNode* node = new TreeNode(max_num);// 进行左右子数组划分int left_left = begin, left_right = max_index;int right_left = max_index + 1, right_right = end;node->left = traversal(nums, left_left, left_right);node->right = traversal(nums, right_left, right_right);return node;}TreeNode* constructMaximumBinaryTree(vector<int>& nums) {return traversal(nums, 0, nums.size());}
};

二、(leetcode 617)合并二叉树

力扣题目链接

状态:AC。

使用的方法可以AC但是不够简洁,留待后续改进

class Solution {
public:TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {//进行前序遍历,如果两棵树都为空则返回空节点if(root1 == nullptr && root2 == nullptr){return nullptr;}TreeNode* node = new TreeNode(0);if(root1 != nullptr && root2 != nullptr){node->val = root1->val + root2->val;node->left = mergeTrees(root1->left, root2->left);node->right = mergeTrees(root1->right, root2->right);}else if(root1){node->val = root1->val;node->left = mergeTrees(root1->left, nullptr);node->right = mergeTrees(root1->right, nullptr);}else{node->val = root2->val;node->left = mergeTrees(nullptr, root2->left);node->right = mergeTrees(nullptr, root2->right);}return node;  }
};

三、(leetcode 700)二叉搜索树中的搜索

力扣题目地址

状态:AC。

简单的前序遍历比较

class Solution {
public:TreeNode* searchBST(TreeNode* root, int val) {if(root == nullptr) return nullptr;//前序遍历if(root->val == val){return root;}else if(root->val < val){return searchBST(root->right, val);}else{return searchBST(root->left, val);}return nullptr;}
};

四、(leetcode 98)验证二叉搜索树

力扣题目链接

状态:思路错误,不能简单地比较根节点和左右子节点的大小。

这道题可以通过中序遍历的顺序判断值是不是递增来判断,注意除了上面的那个思路问题,在实现时用于比较的值maxVal需要使用long long来初始化,以防测试用例中有INT_MIN。

class Solution {
public:long long maxVal = LONG_MIN;bool isValidBST(TreeNode* root) {if(root == nullptr) return true;bool left = isValidBST(root->left);//中序遍历查看是否符合递增if(root->val > maxVal){maxVal = root->val;}else{return false;}bool right = isValidBST(root->right);return left && right;}
};

相关文章:

代码随想录算法训练营第23期day19| 654.最大二叉树、617.合并二叉树、700.二叉搜索树中的搜索、98.验证二叉搜索树

目录 一、&#xff08;leetcode 654&#xff09;最大二叉树 二、&#xff08;leetcode 617&#xff09;合并二叉树 三、&#xff08;leetcode 700&#xff09;二叉搜索树中的搜索 四、&#xff08;leetcode 98&#xff09;验证二叉搜索树 一、&#xff08;leetcode 654&…...

第四章 字符串part02 28. 实现strStr() 459. 重复的子字符串

第四章 字符串part02 28. 实现strStr() 459. 重复的子字符串 一、28. 实现strStr() 题目链接&#xff1a;https://leetcode.cn/problems/repeated-substring-pattern/ 题目介绍&#xff1a; 给定一个非空的字符串 s &#xff0c;检查是否可以通过由它的一个子串重复多次构成。…...

设计模式 - 状态模式

目录 一. 前言 二. 实现 一. 前言 状态模式&#xff08;State Pattern&#xff09;&#xff1a;它主要用来解决对象在多种状态转换时&#xff0c;需要对外输出不同的行为的问题。状态和行为是一一对应的&#xff0c;状态之间可以相互转换。当一个对象的内在状态改变时&#x…...

【vim 学习系列文章 9 -- .vim 脚本文件开发学习】

文章目录 .vimrc 介绍.vim 脚本文件开发 .vimrc 介绍 在Vim中&#xff0c;你可以将一系列的Vim命令和设置写入一个脚本文件中&#xff0c;并使用:source命令来运行它。这种脚本文件通常被称为vimrc文件&#xff0c;因为它的默认名称是.vimrc。通常&#xff0c;我们将这个文件放…...

NAT模式和桥接模式的区别

NAT模式和桥接模式的区别 NAT模式和桥接模式都是虚拟机网络配置的两种方式&#xff0c;主要区别在于虚拟机与外部网络交互的方式不同。 NAT&#xff08;Network Address Translation&#xff0c;网络地址转换&#xff09;模式&#xff1a;在这种模式下&#xff0c;虚拟机和宿主…...

应对出海安全合规挑战,兆珑科技为什么选择了亚马逊云科技?

在中国企业出海进程中&#xff0c;安全合规是企业面临的首要挑战。尤其是当企业业务涉及金融相关领域时&#xff0c;面临着最为严苛的安全合规要求。 深圳兆珑科技有限公司是一家全球化的物联网生态企业&#xff0c;其业务覆盖100多个国家和地区&#xff0c;在欧洲、南美、亚太…...

Allegro基本规则设置指导书之Spacing规则设置

进入规则设置界面 1.设置Line 到其他的之间规则: 2.设置Pins 到其他的之间规则: 3.设置Vias 到其他的之间规则:...

使用【Blob、Base64】两种方式显示【文本、图片、视频】 使用 video 组件播放视频

Blob 显示 Blob 对象的类型是由 MIME 类型&#xff08;Multipurpose Internet Mail Extensions&#xff09;来确定的。MIME 类型是一种标准&#xff0c;用于表示文档、图像、音频、视频等多媒体文件的类型。以下是一些常见的 Blob 对象类型&#xff1a; text/plain&#xff1…...

深度学习_1_基本语法

数据结构 代码&#xff1a; import torchx torch.arange(12)##产生长度为12的一维张量print(x)##X x.resize(3, 4)##被弃用##print(X)y torch.reshape(x, (3, 4))##修改向量为矩阵&#xff0c;一维变二维print(y)print(y.size())xx torch.zeros((2, 3, 4))##三维矩阵&…...

c#设计模式-行为型模式 之 中介者模式

&#x1f680;简介 又叫调停模式&#xff0c;定义一个中介角色来封装一系列对象之间的交互&#xff0c;使原有对象之间的耦合松散&#xff0c;且可以独立地改变它们之间的交互。 从下右图中可以看到&#xff0c;任何一个类的变 动&#xff0c;只会影响的类本身&#xff0c;以及…...

小程序uView2.X框架upload组件上传方法总结+避坑

呈现效果: 1.1单图片上传 1.2多图片上传 前言:相信很多人写小程序会用到uView框架,总体感觉还算OK吧,只能这么说,肯定也会遇到图片视频上传,如果用到这个upload组件相信你,肯定遇到各种各样的问题,这是我个人总结的单图片和多图片上传方法. uView2.X框架:uView 2.0 - 全面兼容…...

人脸检测及追踪回顾

轻量级人脸检测 代码地址 人脸追踪 代码地址 MNN框架部署文档 文档地址...

虚拟环境和包

目录 12. 虚拟环境和包 12.1. 简介 12.2. 创建虚拟环境 12.3. 使用 pip 管理包 12. 虚拟环境和包 12.1. 简介 Python 应用程序经常会使用一些不属于标准库的包和模块。应用程序有时候需要某个特定版本的库&#xff0c;因为它需要一个特定的 bug 已得到修复的库或者它是使用…...

springboot配置文件读取

项目配置文件 怎么说呢&#xff0c;给了个项目&#xff0c;他启动了&#xff0c;然后我看不懂为啥能够启动项目这样 很迷茫&#xff0c;为啥能够成功启动呢项目&#xff0c;为啥项目有properties也要有yml呢&#xff1f; 问题处理 首先&#xff0c;properties的配置的优先级…...

纵享丝滑!Cesium + ffmpegserver 生成高质量动态视频【逐帧生成】

工作中需要提供一些在三维场景下的视频动画素材&#xff0c;屏幕录制会出现掉帧等其他问题&#xff0c;看到 ffmpegserver 后&#xff0c;眼前一亮 Cesium ffmpegserver 生成高质量视频 1.自建 ffmpegserver 首先&#xff0c;克隆 ffmpegserver 仓库代码 git clone https://…...

Linux下C++编程-进度条

引言&#xff1a;本篇主要在linux下的C实现进度条的功能。按照多文件编程&#xff0c;同时使用Makefile文件完成多文件的编译、连接。 首先创建头文件&#xff1a; 1. progress.h #pragma once #include <iostream> #include <cstring> #include <iomanip>…...

C语言常见题目(1)交换两个变量的值,数的逆序输出,猜数游戏,两个数比较大小等

我的个人主页&#xff1a;☆光之梦☆的博客_CSDN博客-C语言基础语法&#xff08;超详细&#xff09;领域博主 欢迎各位 &#x1f44d;点赞 ⭐收藏 &#x1f4dd;评论 特别标注&#xff1a;本博主将会长期更新c语言的语法知识&#xff0c;初学c语言的朋友们&#xff0c;可以收藏…...

Springboot使用sqlcipher4加密sqlite数据库

在有些业务场景&#xff0c;需要使用sqlite数据库&#xff0c;但sqlite数据库生的db文件&#xff0c;是明文的&#xff0c;该文件被别人拿到&#xff0c;就可以看到里面的所有数据&#xff0c;非常不安全&#xff0c;市面上有很多对sqlite数据库文件加密的方式&#xff0c;但都…...

指针拔尖(2)(巩固提高,全网最牛,包会,看不懂带电脑来找我)

文章目录 前言变量的声明 一、函数指针二、函数指针数组三、指向函数指针数组的指针四、 回调函数总结 前言 提示&#xff1a;本章是指针拔尖系列的终章&#xff0c;有四大知识点。 一、函数指针 二、函数指针数组 三、指向函数指针数组的指针 四、回调函数 但学习这些知识点我…...

本地部署多语言代码生成模型CodeGeeX2

&#x1f3e0; Homepage&#xff5c;&#x1f4bb; GitHub&#xff5c;&#x1f6e0; Tools VS Code, Jetbrains&#xff5c;&#x1f917; HF Repo&#xff5c;&#x1f4c4; Paper &#x1f44b; Join our Discord, Slack, Telegram, WeChat BF16/FP16版本&#xff5c;BF16…...

C语言刷题练习(Day2)

✅作者简介&#xff1a;大家好我是&#xff1a;侠客er&#xff0c;是一名普通电子信息工程专业的大学学生&#xff0c;希望一起努力&#xff0c;一起进步&#xff01; &#x1f4c3;个人主页&#xff1a;侠客er &#x1f525;系列专栏&#xff1a;C语言刷题练习 &#x1f3f7;️…...

docker- harbor私有仓库部署与管理

什么是 harbor harbor是一个开源的云原生镜像仓库&#xff0c;它允许用户存储、签名、和分发docker镜像。可以将 harbor 看作是私有的docker hub &#xff0c;它提供了更新安全性和控制性&#xff0c;让组织能够安全的存储和管理镜像 harbor RBAC&#xff08;基于角色访问控制…...

自动化测试的优缺点

自动化测试的优势 能够极大地提升测试的效率&#xff0c;测试人员可以迅速地在指定平台部署测试脚本且对相应功能进行测试。 “弱化”了软件测试人员个体差异对测试结果的影响。 提高整个测试团队的技能水平。 自动化测试的缺陷 自动化测试的缺陷在于&#xff1a;总是按照…...

深度学习基础知识 Dataset 与 DataLoade的用法解析

深度学习基础知识 Dataset 与 DataLoade的用法解析 1、Dataset2、DataLoader参数设置&#xff1a;1、pin_memory2、num_workers3、collate_fn分类任务目标检测任务 1、Dataset 代码&#xff1a; import torch from torch.utils import dataclass MyDataset(torch.utils.data.D…...

【ElasticSearch】深入探索 DSL 查询语法,实现对文档不同程度的检索,以及对搜索结果的排序、分页和高亮操作

文章目录 前言一、Elasticsearch DSL Query 的分类二、全文检索查询2.1 match 查询2.2 multi_match 查询 三、精确查询3.1 term 查询3.2 range 查询 四、地理坐标查询4.1 geo_bounding_box 查询4.2 geo_distance 查询 五、复合查询5.1 function score 查询5.2 boolean 查询 六、…...

使用wireshark解密ipsec ISAKMP包

Ipsec首先要通过ikev2协议来协商自己后续协商所用的加解密key以及用户数据的esp包用的加解密包。 ISAKMP就是加密过的ike-v2的加密包&#xff0c;有时候我们需要解密这个包来查看协商数据。如何来解密这样的包? 首先导出strongswan协商生成的各种key. 要能导出这些key&#…...

算法进阶-搜索

算法进阶-搜索 题目描述&#xff1a;给定一张N个点M条边的有向无环图&#xff0c;分别统计从每个点除法能够到达的点的数量 **数据规模&#xff1a;**1 < n < 3e4 **分析&#xff1a;**这里我们可以使用拓扑排序根据入边对所有点进行排序&#xff0c;排序后我们按照逆序&…...

时空智友企业流程化管控系统 sessionid泄露漏洞 复现

文章目录 时空智友企业流程化管控系统 sessionid泄露漏洞 复现0x01 前言0x02 漏洞描述0x03 影响平台0x04 漏洞环境0x05 漏洞复现1.访问漏洞环境2.构造POC3.复现 时空智友企业流程化管控系统 sessionid泄露漏洞 复现 0x01 前言 免责声明&#xff1a;请勿利用文章内的相关技术从…...

QT编程,QMainWindow、事件

目录 1、QMainWindow 2、事件 1、QMainWindow QMenuBar&#xff1a;菜单栏 QMenu: 菜单 QAction: 动作 QToolBar: 工具栏 QStatusBar: 状态栏 setWindowTitle("主窗口"); //: 前缀 文件名 setWindowIcon(QIcon(":/mw_images/10.png")); resize(640, 4…...

人工智能在教育上的应用2-基于大模型的未来数学教育的情况与实际应用

大家好&#xff0c;我是微学AI ,今天给大家介绍一下人工智能在教育上的应用2-基于大模型的未来数学教育的情况与实际应用&#xff0c;随着人工智能(AI)和深度学习技术的发展&#xff0c;大模型已经开始渗透到各个领域&#xff0c;包括数学教育。本文将详细介绍基于大模型在数学…...