day 20 二叉树 part05
654.最大二叉树
注意类似用数组构造二叉树的题目,每次分隔尽量不要定义新的数组,而是通过下标索引直接在原数组上操作,这样可以节约时间和空间上的开销。
题目链接/文章讲解:代码随想录
lass Solution {
private:// 在左闭右开区间[left, right),构造二叉树TreeNode* traversal(vector<int>& nums, int left, int right) {if (left >= right) return nullptr;// 分割点下标:maxValueIndexint maxValueIndex = left;for (int i = left + 1; i < right; ++i) {if (nums[i] > nums[maxValueIndex]) maxValueIndex = i;}TreeNode* root = new TreeNode(nums[maxValueIndex]);// 左闭右开:[left, maxValueIndex)root->left = traversal(nums, left, maxValueIndex);// 左闭右开:[maxValueIndex + 1, right)root->right = traversal(nums, maxValueIndex + 1, right);return root;}
public:TreeNode* constructMaximumBinaryTree(vector<int>& nums) {return traversal(nums, 0, nums.size());}
};
617.合并二叉树
优先掌握递归。
代码随想录
递归法
class Solution {
public:TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {if (t1 == NULL) return t2;if (t2 == NULL) return t1;// 重新定义新的节点,不修改原有两个树的结构TreeNode* root = new TreeNode(0);root->val = t1->val + t2->val;root->left = mergeTrees(t1->left, t2->left);root->right = mergeTrees(t1->right, t2->right);return root;}
};
迭代法
class Solution {
public:TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {if (t1 == NULL) return t2;if (t2 == NULL) return t1;queue<TreeNode*> que;que.push(t1);que.push(t2);while(!que.empty()) {TreeNode* node1 = que.front(); que.pop();TreeNode* node2 = que.front(); que.pop();// 此时两个节点一定不为空,val相加node1->val += node2->val;// 如果两棵树左节点都不为空,加入队列if (node1->left != NULL && node2->left != NULL) {que.push(node1->left);que.push(node2->left);}// 如果两棵树右节点都不为空,加入队列if (node1->right != NULL && node2->right != NULL) {que.push(node1->right);que.push(node2->right);}// 当t1的左节点 为空 t2左节点不为空,就赋值过去if (node1->left == NULL && node2->left != NULL) {node1->left = node2->left;}// 当t1的右节点 为空 t2右节点不为空,就赋值过去if (node1->right == NULL && node2->right != NULL) {node1->right = node2->right;}}return t1;}
};
700.二叉搜索树中的搜索
递归和迭代都掌握
二叉搜索树的特点是根节点比左孩子节点要大,比右孩子节点要小。
代码随想录
递归法:注意遍历左右子树的时候要返回函数,如果左右子树都遍历不到的时候,就返回空
class Solution {
public:TreeNode* searchBST(TreeNode* root, int val) {if (root == NULL || root->val == val) return root;if (root->val > val) return searchBST(root->left, val);if (root->val < val) return searchBST(root->right, val);return NULL;}
};
class Solution {
public:TreeNode* searchBST(TreeNode* root, int val) {while (root != NULL) {if (root->val > val) root = root->left;else if (root->val < val) root = root->right;else return root;}return NULL;}
};
98.验证二叉搜索树
遇到 搜索树,一定想着中序遍历,这样才能利用上特性。
注意根节点要比所有左子树的所有节点都要小,要比所有右子树的节点都要大。
方法一:maxValue来记录前一个节点的数值,如果前一个节点的数值(按照中序的遍历顺序,数组的值应该是递增的(如果是平衡二叉树的话),否则就不是平衡二叉树)
方法二:用pre记录前一个节点,当前节点和pre进行比较,pre进行更新。
class Solution {
public:TreeNode* pre = NULL; // 用来记录前一个节点bool isValidBST(TreeNode* root) {if (root == NULL) return true;bool left = isValidBST(root->left);if (pre != NULL && pre->val >= root->val) return false;pre = root; // 记录前一个节点bool right = isValidBST(root->right);return left && right;}
};
也可以用迭代法,只用增加一个指针指向前一个节点和判断什么时候返回fasle以及更新前一个指针的。
注意:while中是两个条件是或的情况!!!!
代码随想录
class Solution {
public:bool isValidBST(TreeNode* root) {stack<TreeNode*> st;TreeNode* cur = root;TreeNode* pre = NULL; // 记录前一个节点while (cur != NULL || !st.empty()) {if (cur != NULL) {st.push(cur);cur = cur->left; // 左} else {cur = st.top(); // 中st.pop();if (pre != NULL && cur->val <= pre->val)return false;pre = cur; //保存前一个访问的结点cur = cur->right; // 右}}return true;}
};相关文章:
day 20 二叉树 part05
654.最大二叉树 注意类似用数组构造二叉树的题目,每次分隔尽量不要定义新的数组,而是通过下标索引直接在原数组上操作,这样可以节约时间和空间上的开销。 题目链接/文章讲解:代码随想录 lass Solution { private:// 在左闭右开…...
003 Springboot操作RabbitMQ
Springboot整合RabbitMQ 文章目录 Springboot整合RabbitMQ1.pom依赖2.yml配置3.配置队列、交换机方式一:直接通过配置类配置bean方式二:消息监听通过注解配置 4.编写消息监听发送测试5.其他类型交换机配置1.FanoutExchange2.TopicExchange3.HeadersExcha…...
小猿口算脚本
实现原理:安卓adb截图传到电脑,然后用python裁剪获得两张数字图片,使用ddddocr识别数字,比较大小,再用adb命令模拟安卓手势实现>< import os import ddddocr from time import sleep from PIL import Imagedef …...
从 Reno TCP 到 Scalable TCP,HighSpeed TCP
前文 Scalable TCP 如何优化长肥管道 介绍了 Scalable TCP,但联系另一个类似的算法 HighSpeed TCP(简称 HSTCP),就会看到一个类似从 Reno TCP 经 BIC 到 CUBIC 的路线,但采用了不同的策略。 Reno TCP 经 BIC 到 CUBIC 路线的核心在于 “在长…...
使用Java调用OpenAI API并解析响应:详细教程
使用Java调用OpenAI API并解析响应:详细教程 在现代应用程序中,API调用是一个非常常见的任务。本文将通过一个完整的示例,讲解如何使用Java调用OpenAI的ChatGPT API,并通过ObjectMapper处理JSON响应。本文的示例不仅适用于OpenAI…...
深入学习并发编程中的 synchronized
文章目录 并发编程中的三个问题可见性原子性有序性 了解Java内存模型JMMsynchronized 保证三大特性synchronized 保证原子性synchronized 保证可见性synchronized 保证有序性 synchronized 的特性可重入特性不可中断特性 通过反汇编学习synchronized原理当修饰代码块时当修饰方…...
AMD R9-9950X相比较I9-14900K有哪些提升
AMD R9-9950X相比较I9-14900K有哪些提升?在处理器领域,AMD与英特尔的竞争从未停歇,每一次新品发布都引发业界的高度关注。近日,AMD推出了其新一代桌面级旗舰处理器——Ryzen 9 9950X(简称R9-9950X)…...
计算机毕业设计 基于Python的个性化旅游线路推荐系统的设计与实现 Python+Django+Vue 前后端分离 附源码 讲解 文档
🍊作者:计算机编程-吉哥 🍊简介:专业从事JavaWeb程序开发,微信小程序开发,定制化项目、 源码、代码讲解、文档撰写、ppt制作。做自己喜欢的事,生活就是快乐的。 🍊心愿:点…...
总结:Flink之DataStream各API介绍
一、介绍 本文主要是详细介绍 DataStream<T> 类中的各个方法,并给出它们的使用场景。 二、基本方法 getId(): 作用:返回转换操作的唯一标识符。场景:当需要调试或日志记录时,有时候需要知道操作的 ID。getParallelism(): 作用:获取流的并行度。场景:在优化作业时…...
设计一个日志管理系统,支持多级别日志记录
设计一个日志管理系统,支持多级别日志记录 作为一名Python程序软件专家,我经常被问到关于日志管理系统的设计和实现。今天,我将分享一篇关于设计一个日志管理系统,支持多级别日志记录的博文,希望能够帮助大家更好地理解和使用Python语言。 日志管理系统的需求 在软件开…...
Javascript动态规划算法
JavaScript中的动态规划(Dynamic Programming,简称DP)是一种通过把原问题分解为相对简单的子问题的方式来求解复杂问题的方法。它主要致力于将“合适”的问题拆分成更小的子目标,并通过建立状态转移方程、缓存并复用以往结果以及按…...
Java 循环里怎么删除元素才安全
首先 在 Java 中,当你在循环中遍历集合时,直接删除元素可能会引发 ConcurrentModificationException。为了安全地删除元素,推荐使用 Iterator 来进行删除操作。 以下是使用 Iterator 删除元素的常见模式: import java.util.Arr…...
LabVIEW晶体振荡器自动化测试系统
基于LabVIEW平台的晶体振荡器自动化测试系统解决了传统手工测试晶体振荡器繁琐且易出错的问题。该系统通过高度自动化的测试流程,提高了测试效率和精度,实现了数据的自动采集与处理,适用于电子、通信等领域的晶振测试需求。 项目背景与意义 …...
3.6.xx版本SpringBoot创建基于Swagger接口文档
介绍 基于Swagger构建的JavaAPI文档工具,实现后端功能的测试,并撰写API接口文档。 方法 pom.xml中引入依赖,要注意的是,本依赖使用的SpringBoot版本为3.6.xx <!--Knife4j--><dependency><groupId>com.github.xiaoymin<…...
Oracle 12201非PDBS模式单机部署(静默安装)
一、创建Oracle数据库的用户 groupadd oinstall groupadd dba groupadd asmadmin groupadd asmdba useradd -g oinstall -G dba,asmdba oracle -d /home/oracle passwd oracle二、配置Linux 服务器参数 cat /home/oracle/.bash_profile export ORACLE_HOSTNAMEH_orcle01 expo…...
Python 源码编译安装详解:跨平台指南及完整步骤解析
Python 源码编译安装详解:跨平台指南及完整步骤解析 文章目录 Python 源码编译安装详解:跨平台指南及完整步骤解析一 准备工作1)Ubuntu/Debian2)CentOS/RHEL3)macOS 二 下载 Python 源码三 编译与安装1)解压…...
MQTT vs HTTP:谁更适合物联网?
前言 随着物联网(IoT)技术的飞速发展中,其应用规模和使用场景正在持续扩大,但它关键的流程仍然是围绕数据传输来进行的,因此设备通信协议选择至关重要。 作为两种主要的通信协议,MQTT 协议和 HTTP 协议各…...
小北的技术博客:探索华为昇腾CANN训练营与AI技术创新——Ascend C算子开发能力认证考试(初级)
前言 哈喽哈喽友友们,这里是zyll~(小北)智慧龙阁的创始人及核心技术开发者。在技术的广阔天地里,我专注于大数据与全栈开发,并致力于成为这一领域的新锐力量。通过智慧龙阁这个平台,我期望能与大家分享我的技术心得,共同探索技术的无限可能。 Ascend C编程:小北的技术…...
鸿蒙next开发者第一课02.DevEcoStudio的使用-习题
【习题】DevEco Studio的使用 通过/及格分80/ 满分100 判断题 1. 如果代码中涉及到一些网络、数据库、传感器等功能的开发,均可使用预览器进行预览。F 正确(True)错误(False) 预览器不能进行传感器等特殊功能的开发,需要使用真机开发 2. module.json5文件中的…...
【vue】监听table水平滚动条切换tab后还原位置
有个需求就是切换tab后,原先的table水平滚动条要还原位置(如下图),先说下思路,大致就是 切出页面时 把滚动距离保存到Storage 中,切回来时在恢复 直接上代码 首先table ref指定一下ref"jtable" …...
华为云AI开发平台ModelArts
华为云ModelArts:重塑AI开发流程的“智能引擎”与“创新加速器”! 在人工智能浪潮席卷全球的2025年,企业拥抱AI的意愿空前高涨,但技术门槛高、流程复杂、资源投入巨大的现实,却让许多创新构想止步于实验室。数据科学家…...
ubuntu搭建nfs服务centos挂载访问
在Ubuntu上设置NFS服务器 在Ubuntu上,你可以使用apt包管理器来安装NFS服务器。打开终端并运行: sudo apt update sudo apt install nfs-kernel-server创建共享目录 创建一个目录用于共享,例如/shared: sudo mkdir /shared sud…...
基于Flask实现的医疗保险欺诈识别监测模型
基于Flask实现的医疗保险欺诈识别监测模型 项目截图 项目简介 社会医疗保险是国家通过立法形式强制实施,由雇主和个人按一定比例缴纳保险费,建立社会医疗保险基金,支付雇员医疗费用的一种医疗保险制度, 它是促进社会文明和进步的…...
关于nvm与node.js
1 安装nvm 安装过程中手动修改 nvm的安装路径, 以及修改 通过nvm安装node后正在使用的node的存放目录【这句话可能难以理解,但接着往下看你就了然了】 2 修改nvm中settings.txt文件配置 nvm安装成功后,通常在该文件中会出现以下配置&…...
NLP学习路线图(二十三):长短期记忆网络(LSTM)
在自然语言处理(NLP)领域,我们时刻面临着处理序列数据的核心挑战。无论是理解句子的结构、分析文本的情感,还是实现语言的翻译,都需要模型能够捕捉词语之间依时序产生的复杂依赖关系。传统的神经网络结构在处理这种序列依赖时显得力不从心,而循环神经网络(RNN) 曾被视为…...
C#中的CLR属性、依赖属性与附加属性
CLR属性的主要特征 封装性: 隐藏字段的实现细节 提供对字段的受控访问 访问控制: 可单独设置get/set访问器的可见性 可创建只读或只写属性 计算属性: 可以在getter中执行计算逻辑 不需要直接对应一个字段 验证逻辑: 可以…...
算法打卡第18天
从中序与后序遍历序列构造二叉树 (力扣106题) 给定两个整数数组 inorder 和 postorder ,其中 inorder 是二叉树的中序遍历, postorder 是同一棵树的后序遍历,请你构造并返回这颗 二叉树 。 示例 1: 输入:inorder [9,3,15,20,7…...
【1】跨越技术栈鸿沟:字节跳动开源TRAE AI编程IDE的实战体验
2024年初,人工智能编程工具领域发生了一次静默的变革。当字节跳动宣布退出其TRAE项目(一款融合大型语言模型能力的云端AI编程IDE)时,技术社区曾短暂叹息。然而这一退场并非终点——通过开源社区的接力,TRAE在WayToAGI等…...
Python第七周作业
Python第七周作业 文章目录 Python第七周作业 1.使用open以只读模式打开文件data.txt,并逐行打印内容 2.使用pathlib模块获取当前脚本的绝对路径,并创建logs目录(若不存在) 3.递归遍历目录data,输出所有.csv文件的路径…...
claude3.7高阶玩法,生成系统架构图,国内直接使用
文章目录 零、前言一、操作指南操作指导 二、提示词模板三、实战图书管理系统通过4o模型生成系统描述通过claude3.7生成系统架构图svg代码转换成图片 在线考试系统通过4o模型生成系统描述通过claude3.7生成系统架构图svg代码转换成图片 四、感受 零、前言 现在很多AI大模型可以…...
