二叉树优选算法（一）
一、根据二叉树创建字符串
题目介绍：
给你二叉树的根节点 root ，请你采用前序遍历的方式，将二叉树转化为一个由括号和整数组成的字符串，返回构造出的字符串。
空节点使用一对空括号对 "()" 表示，转化后需要省略所有不影响字符串与原始二叉树之间的一对一映射关系的空括号对。
- 树中节点的数目范围是
[1, 104] -1000 <= Node.val <= 1000
思路：
这个题就是一个简单的开胃菜，思路就是在前序遍历的过程中先将所有子树都用括号括起来，最后看哪些括号可以省略，观察可以发现，如果左子树不为空，右子树为空，那么右子树括号就可以省略，如果左子树为空，右子树不为空，那左子树的括号不能省略，所以右子树存在就打印括号，不存在就不打印，而左子树存在则一定打印，如果为空的话就要看右子树是否存在
class Solution {
public:string tree2str(TreeNode* root) {string str;if (root == nullptr)return str;str += to_string(root->val);if (root->left||(root->left==nullptr&&root->right)) {str += '(';str+=tree2str(root->left);str += ')';}if (root->right) {str += '(';str+=tree2str(root->right);str += ')';}return str;}
};二、二叉树的层序遍历
题目介绍：
给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。
思路1：
对于层序遍历来说很简单，只需要利用一个队列即可，首先将根节点放入队列，在每次出一个节点时，就将这个节点的左右结点放入队列，直到队列为空就遍历完成了，但是这个题目要求我们将每一层的节点数据放到一个数组中，但是我们不知道队列中的每个数据是哪一层的，所以我们可以再创建一个队列，用于记录对应节点的层数
这里就需要两层循环，一层遍历每一层，一层遍历每一层的数据
class Solution {
public:vector<vector<int>> levelOrder(TreeNode* root) {vector<vector<int>> vv;queue<TreeNode*> q; // 保存结点queue<int> qlevel; // 保存结点的层数int level = 1;if (root) {q.push(root);qlevel.push(level);}while (!q.empty()) {vector<int> v;while (level == qlevel.front()) {qlevel.pop();TreeNode* node = q.front();q.pop();v.push_back(node->val);if (node->left) {q.push(node->left);qlevel.push(level+1);}if (node->right) {q.push(node->right);qlevel.push(level+1);}}level++;vv.push_back(v);}return vv;}
};思路2：
基于思路1进行优化，我们无非就是需要知道队列中的数据是对应哪一层的，如果我们知道每一层的数据个数，那就很容易控制队列，所以我们就在遍历完一层后，可以根据队列中的数据个数确定下一层的数据个数levelSize，因为上一层的数据都被出去了，而下一层的数据也都被放入队列了。
和上面一样这里也是两层循环
class Solution {
public:vector<vector<int>> levelOrder(TreeNode* root) {vector<vector<int>> vv;queue<TreeNode*> q;int leveSize=0;if (root) {q.push(root);leveSize = 1;}while (leveSize > 0) {vector<int> v;while (leveSize--) {TreeNode* node = q.front();v.push_back(node->val);q.pop();if (node->left) {q.push(node->left);}if (node->right) {q.push(node->right);}}leveSize = q.size();vv.push_back(v);}return vv;}
};补充：
这里还有一个类似的引申题目
给你二叉树的根节点 root ，返回其节点值 自底向上的层序遍历 。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）
与上述题目不同的是，他的要求是倒着遍历，那我们可以先正向遍历，最后将结果翻转一下
reverse(vv.begin(), vv.end());三、二叉树的最近公共祖先
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
思路1：
最近公共祖先有两种情况，如果一个节点1在另一个节点2的子树中，那节点2就是公共祖先。如果不是上述的情况，那这两个节点一定一个在公共祖先的左边，一个在右边。
对于一个节点来说，p和q和他的位置关系有三种
- 一个在左一个在右（找到了）
- 都在左（那公共节点一定在左边，往左边找）
- 都在右（那公共节点一定在右边，往右边找）
class Solution {
public:bool IsChildTree(TreeNode* root, TreeNode* x) {if (root == nullptr)return false;if (root == x)return true;return IsChildTree(root->left, x) || IsChildTree(root->right, x);}TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {// 发现规律：这两个节点一定一个在最近的公共祖先的左边,一个在右边// 或者一个节点是另一个节点的子孙节点if (root == nullptr)return nullptr;if (root == p || root == q)return root;bool pInLeft,pInRight,qInLeft,qInRight;pInLeft=IsChildTree(root->left,p);pInRight=!pInLeft;qInLeft=IsChildTree(root->left,q);qInRight=!qInLeft;//一个在左一个在右if((pInLeft&&qInRight)||(pInRight&&qInLeft)){return root;}else if(pInLeft&&qInLeft) //都在左边{return lowestCommonAncestor(root->left,p,q);}else //都在右边{return lowestCommonAncestor(root->right,p,q);}}
};但是上面的解法时间复杂度比较高，在最坏的情况下可以到达O(n^2)，因为每次都需要判断两个节点是不是他的子树，如果这个两个节点在靠下的位置，每次判断都需要遍历查找到最下面
思路2：
如果我们有了两个节点到根节点的路径，那么这个题目就可以转变为链表相交的问题
所以重点就到了如何获取一个节点到跟节点的路径，我们可以利用栈，使用前序遍历这个树，碰到一个节点首先把它入栈，因为即使这个节点不是我们要找的节点，这个节点也可能是路径中的一个分支，然后继续遍历他的两个子树，如果他的两个子树都没找到，说明这个节点一定不属于路径中，就把这个节点弹出去。
当获取到两个节点到根节点的路径，首先让长的路径先走，直到两个链表的长度相同，在一块走，直到找到相交点
class Solution {
public:bool GetPath(TreeNode* root, TreeNode* x, stack<TreeNode*>& path) {if (root == nullptr)return false;// 前序遍历的思路，找x结点的路径// 遇到root结点先push⼊栈，因为root就算不是x，但是root可能是根->x路径中⼀个分⽀结点 path.push(root);if (root == x)return true;if (GetPath(root->left, x, path))return true;if (GetPath(root->right, x, path))return true;// 如果左右⼦树都没有x，那么说明上⾯⼊栈的root不是根->x路径中⼀个分⽀结点// 所以要pop出栈，回退，继续去其他分⽀路径进⾏查找path.pop();return false;}TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {stack<TreeNode*> pPath, qPath;GetPath(root, p, pPath);GetPath(root, q, qPath);// 模拟链表相交，两个路径找交点// ⻓的先⾛差距步，再⼀起⾛找交点while (pPath.size() != qPath.size()) {if (pPath.size() > qPath.size())pPath.pop();elseqPath.pop();}while (pPath.top() != qPath.top()) {pPath.pop();qPath.pop();}return pPath.top();}
};
相关文章：
二叉树优选算法（一）
一、根据二叉树创建字符串 题目介绍： 给你二叉树的根节点 root ，请你采用前序遍历的方式，将二叉树转化为一个由括号和整数组成的字符串，返回构造出的字符串。 空节点使用一对空括号对 "()" 表示，转化后需…...
单片机C51--笔记8-STC89C51RC/RD-IIC协议
一、概述 IIC全称Inter-Integrated Circuit (集成电路总线) 是由PHILIPS公司在80年代开发的两线式串行总线，用于连接微控制器及其外围设备。IIC属于半双 工同步通信方式。 特点 简单性和有效性。 由于接口直接在组件之上，因此IIC总线占用的空间非常小…...
HttpUtil的get和post请求
Http工具类 import org.apache.http.Consts; import org.apache.http.HttpEntity; import org.apache.http.HttpResponse; import org.apache.http.client.entity.UrlEncodedFormEntity; import org.apache.http.client.methods.CloseableHttpResponse; import org.apache.ht…...
leetcode 二进制数转字符串
1.题目要求: 2.题目代码: class Solution { public:string printBin(double num) {string result;double compare_value 1.0;//先给把0和.赋值给result;result.push_back(0);result.push_back(.);while(result.size() < 33){//利用十进制转换成二进制的方法//1.先给num …...
前端项目使用gitlab-cicd+docker实现自动化部署
GitLab CI/CD 是一个强大的工具，可以实现项目的自动化部署流程，从代码提交到部署只需几个步骤。本文将带你配置 GitLab CI/CD 完成一个前端项目的自动化部署。 前言 为什么使用cicddocker？ 目前我们公司开发环境使用的shell脚本部署&#…...
【Linux】进程
🌻个人主页：路飞雪吖~ 🌠专栏：Linux 目录 一、冯诺依曼体系结构 🌟系统调用和库函数概念 二、操作系统OS 三、进程 🌟查看进程 🌟通过系统调用获取进程标示符 🌟通过系统调用创…...
transformers生成式对话机器人
简介 生成式对话机器人是一种先进的人工智能系统，它能够通过学习大量的自然语言数据来模拟人类进行开放、连贯且创造性的对话。与基于规则或检索式的聊天机器人不同，生成式对话机器人并不局限于预定义的回答集，而是可以根据对话上下文动态地…...
Text2SQL（NL2sql）对话数据库：设计、实现细节与挑战
Text2SQL（NL2sql）对话数据库：设计、实现细节与挑战 前言1.何为Text2SQL（NL2sql）2.Text2SQL结构与挑战3.金融领域实际业务场景4.注意事项5.总结 前言 随着信息技术的迅猛发展，人机交互的方式也在不断演进。…...
)
C# 关于加密技术以及应用(二)
AES（Advanced Encryption Standard）和 RSA（Rivest-Shamir-Adleman）是两种不同的加密算法，它们各自有特定的使用场景和优势。下面是它们的主要区别和适用场景： AES（高级加密标准） 特…...
四十四：Web如何关闭会话
在Web应用中，关闭会话（Session Termination）是一个重要的机制，用于确保用户的会话状态被安全地终止。无论是用户主动退出登录还是因超时被动登出，正确地管理会话关闭有助于提升安全性并释放服务器资源。 一、为什么需…...
在wsl2中安装archlinux
在之前的博客中，我介绍了如何在虚拟机或者真实机上安装archlinux并且进行一定的配置，但是实际上Linux不管怎么配置在日常使用中都没有Windows简单便利，在开发有关Linux的程序时过去用虚拟机或者直接在Windows上使用ssh在远程服务器上进行开发…...
在Goland中对goroutine协程断点调试
在Goland中对goroutine协程断点调试 环境: Goland 参考了 chatgpt 的回复 进行断点调试的代码 package mainimport ("fmt""sync""time" )// worker 模拟处理任务 func worker(id int, wg *sync.WaitGroup) {defer wg.Done() // 确保任务完成后…...
最长连续递增序列
问题分解 1：要求 要求找到最长的连续递增子序列，即在原数组中位置连续且数值严格递增的一段序列 2：输入和输出 输入是一个未经排序的整数数组nums 输出是该数组中最长连续递增子序列的长度 3：边界调节 数组为空则长度为0 …...
apt 包 源 的维护 和缓存 命令
APT 包源维护命令 更新软件包列表： sudo apt update：从配置的软件源中获取最新的软件包信息。这是安装、升级或删除软件包前通常要执行的步骤，以确保使用的是最新的软件包信息。 升级软件包： sudo apt upgrade：升级系…...
【排序方法的总结】
在数据结构中常见的排序方法有： 插入排序、交换排序、选择排序、归并排序和基数排序等。 插入排序 特点： 简单直观，对于小规模的数据排序效率较高。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后…...
工作中常用springboot启动后执行的方法
前言： 工作中难免会遇到一些，程序启动之后需要提前执行的需求。 例如： 初始化缓存：在启动时加载必要的缓存数据。定时任务创建或启动：程序启动后创建或启动定时任务。程序启动完成通知：程序启动完成后通…...
QT 中使用 QTableView 和 QStandardItemModel 实现将数据导出到Excel 和 从Excel导入到 QTableView 的功能
简介 在Qt中，使用QTableView和QStandardItemModel来实现将数据导出到Excel和从Excel导入到QTableView的功能，而不使用第三方库（如QXlsx）。 效果 将 QTableView 中的数据导出到Excel //从tableview 导出到 EXcle void MainInterfa…...
模版方法模式的理解和实践
在软件开发中，设计模式为我们提供了一套经过验证的解决方案，用于解决常见的设计问题。其中，模版方法模式（Template Method Pattern）是一种行为设计模式，它定义了一个算法的框架，并允许子类在不改…...
05-树莓派-交叉编译
交叉编译的概念 交叉编译是什么 来源百度百科： 交叉编译是在一个平台上生成另一个平台上的可执行代码。同一个体系结构可以运行不同的操作系统；同样，同一个操作系统也可以在不同的体系结构上运行。 举例来说，我们常说的x86 Lin…...
杨振宁大学物理视频中黄色的字，c#写程序去掉
先看一下效果：（还有改进的余地） 我的方法是笨方法，也比较刻板。 1，首先想到，把屏幕打印下来。c#提供了这样一个函数： Bitmap bmp new Bitmap(640, 480, PixelFormat.Format32bppArgb); // 创…...
非归档模式下一个或多个数据文件损坏恢复
1. 介绍 有些时侯可能你的库处于非归档的模式下，而你的联机重做日志又currupted,你的数据文件不能完成完全的恢复，这里为大家介绍一个oracle的一个隐藏参数_allow_resetlogs_corruption，让数据库重生。 通过设置隐含参数恢复 alter system …...
k8s 之storageclass使用nfs动态申请PV
文章目录 配置角色权限部署nfs-client-provisioner创建 NFS StorageClass创建 PVC 来动态申请 PV在 Pod 中使用 PVC验证存储是否正确挂载使用 kubectl 和 jq 筛选 PVCwaiting for a volume to be created, either by external provisioner "nfs-diy" or manually cre…...
Spark实训
实训目的： 介绍本实训的基本内容，描述知识目标、，以及本实训的预期效果等。 1、知识目标 （1）了解spark概念、基础知识、spark处理的全周期，了解spark技术是新时代对人才的新要求。 （2）掌握Linux、hadoop、spark、hive集群环境的搭建、HDFS分布文件系统的基础知识与应用…...
)
Mitel MiCollab 企业协作平台 任意文件读取漏洞复现(CVE-2024-41713)
0x01 产品简介 Mitel MiCollab是加拿大Mitel（敏迪）公司推出的一款企业级协作平台，旨在为企业提供统一、高效、安全的通信与协作解决方案。通过该平台，员工可以在任何时间、任何地点，使用任何设备，实现即时通信、语音通话、视频会议、文件共享等功能，从而提升工作效率和…...
React学习笔记（一）
创建函数写法一： 重点：函数有几种写法 function DemoShow() {return (<div className"App">函数声明</div>); }export default DemoShow;对应js创建函数声明：function sum1(a,b){return ab } 创建函数写法二&#x…...
【H2O2|全栈】MySQL的基本操作（三）
目录 前言 开篇语 准备工作 案例准备 多表查询 笛卡尔积 等值连接 外连接 内连接 自连接 子查询 存在和所有 含于 分页查询 建表语句 结束语 前言 开篇语 本篇继续讲解MySQL的一些基础的操作——数据字段的查询中的多表查询和分页查询，与单表查询…...
SQL按指定字符分割字符串
在SQL中分割字符串通常需要使用特定的函数，因为SQL本身并不像编程语言那样直接支持字符串分割。不同的数据库系统有不同的函数来处理字符串分割。以下是一些常见数据库系统中分割字符串的方法： 1. MySQL 在MySQL中，你可以使用SUBSTRING_IND…...
NAT traversal 原理 | TCP / UDP/ P2P
注：本文为 “NAT traversal ”相关的几篇文章合辑。 未整理去重。 NAT 穿越技术原理 Li_yy123 于 2020-12-08 18:54:26 发布 一、NAT 由来 为了解决全球公有 IPv4 的稀缺，提出了 NAT 技术。NAT 是 Network Address Translation 网络地址转换的缩写。 …...
喜报！极限科技（INFINI Labs）通过国家高新技术企业认定
2024 年 10 月 29 日，国家高新技术企业认定管理工作网公示了北京市认定机构 2024 年认定报备的第一批高新技术企业备案名单，极限数据（北京）科技有限公司 顺利通过本次高新技术企业评审，并获得 国家级“高新技术企业”认…...
在Ubuntu 22.04上搭建Kubernetes集群
Kubernetes 简介 什么是 Kubernetes？ Kubernetes（常简称为 K8s）是一个强大的开源平台，用于管理容器化应用程序的部署、扩展和运行。它最初由 Google 设计并捐赠给 Cloud Native Computing Foundation（CNCF࿰…...
【OpenCV】平滑图像
二维卷积(图像滤波) 与一维信号一样，图像也可以通过各种低通滤波器（LPF）、高通滤波器（HPF）等进行过滤。LPF 有助于消除噪音、模糊图像等。HPF 滤波器有助于在图像中找到边缘。 opencv 提供了函数 **cv.filter2D()**&…...
Vue了解
MVVM和MVC区别是什么? MVC ： 传统的设计模式。 设计模式： 一套广泛被使用的开发方式 M： model 模型 模型：就是数据的意思 V ： view视图 视图：就是页面的意思 C：controlle…...
JS 深拷贝浅拷贝
一、浅拷贝 // 假设有一个JSON对象 let originalObject {name: "Alice",age: 25,interests: ["reading", "coding"] };// 将JSON对象赋值给另一个变量 let copiedObject originalObject;// 修改新变量的属性 copiedObject.age 26;// 输出原始…...
设计模式学习之——单例模式
单例模式（Singleton Pattern）是一种创建型设计模式，它确保一个类只有一个实例，并提供一个全局访问点来获取该实例。这个模式的主要目的是控制对象的创建，确保在程序的整个生命周期中，某个类只有一个实例被创…...
Linux Vi/Vim使用 ⑥
掌握 CentOS 7 下的 Vi/Vim 编辑器：从安装到精通 在 CentOS 7 系统的日常运维、编程开发以及各类文本处理场景中，Vi/Vim 编辑器都是不可或缺的得力工具。它以轻量、高效、功能强大著称，虽然初次上手有一定学习门槛，但掌握之后便能…...
【5G】5G技术组件 5G Technology Components
5G的目标设置非常高，不仅在数据速率上要求达到20Gbps，在容量提升上要达到1000倍，还要为诸如大规模物联网（IoT， Internet of Things）和关键通信等新服务提供灵活的平台。这些高目标要求5G网络采用多种新技术…...
Java 学习，字符串比较
Java 字符串比较通常使用 equals() 方法，而不是使用 运算符。因为 运算符，比较的是字符串对象的引用是否相同，而 equals() 方法比较的是字符串的内容是否相同。 使用equals()等方法，比较两个字符串： public class …...
普通算法——二维前缀和
二维前缀和 题目链接：https://www.acwing.com/problem/content/798/ 题目描述： 输入一个 n n n 行 m m m 列的整数矩阵，再输入 q q q 个询问，每个询问包含四个整数 ** x 1 , y 1 , x 2 , y 2 x1,y1,x2,y2 x1,y1,x2,y2 &…...
2024年API接口发展趋势：智能化、自动化引领潮流
随着信息技术的飞速发展，应用程序编程接口（API）已成为现代软件开发的核心组成部分。API作为不同系统之间的桥梁，使得数据、功能和服务能够在各种平台和设备之间无缝流动。在2024年，API接口正经历着一系列显著的变革和发…...
SQL中的通配符：使用LIKE操作符进行模式匹配
在SQL中，LIKE 操作符用于在查询中进行模式匹配。它常用于 WHERE 子句中，以便根据特定模式查找数据。与直接进行精确匹配的 操作符不同，LIKE 允许你使用通配符来对数据进行模糊查询，从而使查询更加灵活和强大。 常见的SQL通配符 …...
数据结构：数组
线性表: 线性表就是数据排成像一条线一样的结构.每个现行表上的数据最多只有前和后两个方向.常见的线性表结构：数组，链表、队列、栈等。 什么是数组: 数组（Array）是一种线性表数据结构。它用一组连续的内存空间，来存储…...
2022 年“泰迪杯”数据分析技能赛A 题竞赛作品的自动评判
2022 年“泰迪杯”数据分析技能赛A 题竞赛作品的自动评判 完整代码请私聊 博主 一、背景 在各类学科竞赛中，常常要求参赛者提交 Excel 或/和 PDF 格式的竞赛作品。 本赛题以某届数据分析竞赛作品的评阅为背景，要求参赛者根据给定的评分准则和标准答案&a…...
java+ssm+mysql美妆论坛
项目介绍： 使用javassmmysql开发的美妆论坛，系统包含超级管理员，系统管理员、用户角色，功能如下： 用户：主要是前台功能使用，包括注册、登录；查看论坛板块和板块下帖子；…...
MySQL | 尚硅谷 | 第13章_约束
MySQL笔记：第13章_约束 文章目录 MySQL笔记：第13章_约束第13章_约束 1. 约束(constraint)概述1.1 为什么需要约束1.2 什么是约束1.3 约束的分类演示代码 2. 非空约束2.1 作用2.2 关键字2.3 特点2.4 添加非空约束2.5 删除非空约束演示代码 3. 唯一性约束3…...
【Ubuntu】Ubuntu的Desktop（学习/用户使用）和Bit版本（工作）
这篇文章似乎没什么必要写，但想了想还是决定记录一下，也许对新手入坑Ubuntu会有帮助， 事实上也很简单，一个是桌面版本，另一个是字符界面版本。 桌面版：拥有图形桌面 字符界面，易上手ÿ…...
面试之MySQL自增ID耗尽问题的解决方案详解
自增ID耗尽问题的解决方案详解 目录 引言切换到BIGINT分表分库UUID雪花算法（Snowflake）回收已删除的ID其他策略策略选择和实施总结 引言 在现代数据库应用中，自增ID作为主键被广泛使用。随着数据量的不断增长，自增ID耗尽问题逐…...
数据结构第一弹-平衡树
大家好，今天和大家一起分享一下数据结构中的平衡树~ 平衡树是一种特别重要的数据结构，它通过维持树的高度来保证操作的效率，从而在众多数据结构中脱颖而出。我们今天深入探讨平衡树的概念、种类、工作原理以及应用实例。 1. 平衡树简介 平衡…...
k8s二进制部署集群报错
k8s二进制部署的集群 添加node节点之后 部署服务之后出现报错 在该节点上telnet 172.30.0.1 443也不通 其他正常节点telnet是通的 解决办法： 修改kube-proxy的服务配置 systemctl daemon-reload systemctl restart kube-proxy再次telnet通了...
深入了解架构中常见的4种缓存模式及其实现
4种缓存模式 随着应用程序的复杂性日益增加，缓存管理变得至关重要。缓存不仅能有效减轻数据库负载，还能显著提升数据访问速度。选择合适的缓存模式能够在不同的业务场景下发挥出最佳效果。 本文将详细介绍四种常见的缓存模式：Cache-Aside (…...
python pyqt5 优秀的开源项目
目录 1. Qutebrowser 2. Anki 3. Calibre 4. Spyder 5. Leo Editor 6. Trelby 7. Eric IDE 8. Fman 9. Gramps 10. OpenShot 使用 PyQt5 开发的优秀开源项目涵盖了各种应用领域，包括桌面应用、开发工具、教育软件等。以下是一些值得关注的 PyQt5 开源项目： 1. Qut…...