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

【20230211】【剑指1】搜索与回溯算法II

  1. 树的子结构

递归思维:对称性递归

什么是对称性递归?就是对一个对称的数据结构(这里指二叉树)从整体的对称性思考,把大问题分解成子问题进行递归,即不是单独考虑一部分(比如树的左子树),而是同时考虑对称的两部分(左右子树),从而写出对称性的递归代码。

题型分类:

可以用对称性递归解决的二叉树问题大多是判断性问题(bool类型函数),这一类问题又可以分为以下两类:

1、不需要构造辅助函数。这一类题目有两种情况:第一种是单树问题,且不需要用到子树的某一部分(比如根节点左子树的右子树),只要利用根节点左右子树的对称性即可进行递归。第二种是双树问题,即本身题目要求比较两棵树,那么不需要构造新函数。

2、需要构造辅助函数。这类题目通常只用根节点子树对称性无法完全解决问题,必须要用到子树的某一部分进行递归,即要调用辅助函数比较两个部分子树。形式上主函数参数列表只有一个根节点,辅助函数参数列表有两个节点。


思路:

此题与572. 另一棵树的子树非常相似,但判断方式不一样。

子结构要么是它本身,要么在它的左子树里面,要么在它的右子树里面。

a) 所以在isSubStructure函数里面要判断是A自身,还是A的左边或右边与B对应 ;

return compare(A, B) || isSubStructure(A->left, B) || isSubStructure(A->right, B);

b) 每次如果匹配失败,必须让B从头开始匹配,而不是直接单层递归compare(A->left,B)||compare(A->right,B),因为此时的B可能是上一层递归传过来的B->next,并不是B真正的根节点;

在递归第一层的时候要检查B是否为空,如果刚开始B就是空树,那么肯定不是子结构;

compare函数里面需要判断:

a) 当B遍历完了,A也遍历完了或者B遍历完了,A还没遍历完,那么B就是子结构;

b) 当A遍历完了,B还没遍历完,说明B不是子结构;

c) 如果AB都没完,但是当前结点值不想等,那么肯定不是子结构;

d) 此时AB都没完,值也相等,那么接着在compare函数里面找AB对应的左右孩子是否相对应;

class Solution {
public:bool compare(TreeNode* A,TreeNode* B){//如果B遍历完,A还没遍历完,那么B是子结构,或者A和B都正好遍历完(前提是遍历过程中都匹配上)if(B==NULL) return true;//如果A遍历完,B还没完,那么B不是子结构if(A==NULL) return false;//如果两个都不空,节点值不同,那么不是子结构if(A->val!=B->val)  return false;//如果现在节点值和子树节点值相同,再分别检查两个的左右孩子return compare(A->left,B->left)&&compare(A->right,B->right);}bool isSubStructure(TreeNode* A, TreeNode* B) {if(B==NULL) return false;if(A==NULL) return false;//要么本身比较,要么是它的左子树,要么是右子树return compare(A,B)||isSubStructure(A->left,B)||isSubStructure(A->right,B);}
};

2.二叉树的镜像(翻转二叉树)

将二叉树的左右孩子交换即可

class Solution {
public:TreeNode* mirrorTree(TreeNode* root) {if(root==NULL)  return NULL;swap(root->left,root->right);mirrorTree(root->left);mirrorTree(root->right);return root;}
};

3.对称的二叉树

其实我们要比较的是两个树(这两个树是根节点的左右子树),所以在递归遍历的过程中,也是要同时遍历两棵树。

class Solution {
public:bool compare(TreeNode* left,TreeNode* right){//首先排除空节点情况if(left==NULL&&right==NULL) return true;else if(left!=NULL&&right==NULL)    return false;else if(left==NULL&&right!=NULL)    return false;//排除值不同的情况else if(left->val!=right->val)  return false;//此时左右节点的数值相同,这时再往下做递归//对于左子树而言  左右中  //对于右子树而言  右左中bool outside=compare(left->left,right->right);bool inside=compare(left->right,right->left);return outside&&inside;}bool isSymmetric(TreeNode* root) {if(root==NULL)  return true;return  compare(root->left,root->right);}
};

相关文章:

【20230211】【剑指1】搜索与回溯算法II

树的子结构递归思维:对称性递归什么是对称性递归?就是对一个对称的数据结构(这里指二叉树)从整体的对称性思考,把大问题分解成子问题进行递归,即不是单独考虑一部分(比如树的左子树),而是同时考…...

STM32F103C8T6—库函数应用I2C/SPI驱动OLED显示中文、字符串

文章目录1. I2C与SPI通信协议对比2. 四脚OLED与六脚OLED3. I2C驱动OLED显示oled.h & oled.c:汉字取模 & oledfont.h:main.c 显示示例:连线方法:4. SPI驱动OLED显示1. I2C与SPI通信协议对比 I2C(Inter-Integra…...

sql语句要注意的地方及常用查询语句

sql要注意的地方关键字不能被缩写,也不能分行小写大写不敏感,没区别使用缩进提高语句的可读性常用查询语句1.查询所有库SHOW DATABASES;2.选择数据库 use 数据库名USE myemployees;3.查看数据库中所有表show tables4.查看表中的内容 select 字段一&#…...

数组去重、伪数组和真数组的区别以及伪数组如何转换成真数组

1.数组去重 1&#xff09; 利用数组的indexOf下标属性来查询。 如果找到一个 item&#xff0c;则返回 item 的第一次出现的位置。开始位置的索引为 0。 如果在数组中没找到指定元素则返回 -1。 function unique4(arr) {var newArr []for (var i 0; i < arr.length; i) {i…...

JavaScript内置支持类Array

<!DOCTYPE html> <html> <head> <meta charset"utf-8"> <title>内置支持类Array</title> </head> <body bgcolor"antiquewhite"> <script type"text/javasc…...

GitLab CI-CD 学习笔记

概述 1. CI/CD CI&#xff08;持续集成&#xff09;指开发人员一天内进行多次合并和提交代码操作&#xff0c;并通过自动化测试&#xff0c;完成构建 CD&#xff08;持续部署&#xff09;指每次代码更改都会自动部署到对应环境 CI/CD 结合在一起&#xff0c;可以加快开发团…...

K8S安装

1.创建三台centos虚拟机 使用的官方最小镜像安装 CentOS-7-x86_64-Minimal-1804.iso 建议最小硬件配置&#xff1a;2核CPU、2G内存、20G硬盘 master配置详情 node1和node2配置详情 三台虚拟机在安装centos的时候在网络IPV4指定DHCP,配置IPV4固定地址&#xff0c;保证可以访问…...

【C++】模板初阶STL简介

今天&#xff0c;你内卷了吗&#xff1f; 文章目录一、泛型编程二、函数模板&#xff08;显示实例化和隐式实例化&#xff09;1.函数模板格式2.单参数模板3.多参数模板4.模板参数的匹配原则三、类模板&#xff08;没有推演的时机&#xff0c;统一显示实例化&#xff09;1.类模…...

备战蓝桥杯第一天【二分查找无bug版】

&#x1f339;作者:云小逸 &#x1f4dd;个人主页:云小逸的主页 &#x1f4dd;Github:云小逸的Github &#x1f91f;motto:要敢于一个人默默的面对自己&#xff0c;强大自己才是核心。不要等到什么都没有了&#xff0c;才下定决心去做。种一颗树&#xff0c;最好的时间是十年前…...

Java集合中的Map

MapMap接口键 值 对存储键不能重复&#xff0c;值可以重复Map三个实现类的存储结构HashMap&#xff1a;Hash表链表红黑树结构 线程不安全TreeMap&#xff1a; 底层红黑树实现HashTable&#xff1a;hash表链表红黑树 线程安全HashMapHashMap常用方法HashMap<String,String>…...

【java】springboot项目启动数据加载内存中的三种方法

文章目录一、前言二、加载方式2.1、 第一种&#xff1a;使用PostConstruct注解&#xff08;properties/yaml文件&#xff09;。2.2、 第二种&#xff1a;使用Order注解和CommandLineRunner接口。2.3、 第三种&#xff1a;使用Order注解和ApplicationRunner接口。三、代码示例3.…...

【GO】29.go-gin支持ssl/tls,即https示例

本文为演示采用自签名证书一.生成证书通过openssl工具生成证书1.1 安装opensslmacos通过brew安装brew install openssl1.2 生成跟证书私钥openssl genrsa -out ca.key 40961.3 准备配置文件vim ca.conf内容如下[ req ] default_bits 4096 distinguished_name req_disti…...

逻辑仿真工具VCS的使用-Makefile

Gvim写RTL code&#xff0c;VCS仿真&#xff0c;Verdi看波形&#xff0c;DC做综合下约束&#xff0c;Primetime做STA&#xff0c;Spyglass做异步时序分析。 VCS全称Verilog Computer Simulation &#xff0c;VCS是逻辑仿真EDA工具的编译源代码的命令。要用VCS做编译仿…...

信息系统安全技术

一、信息安全的有关概念 1. 属性2. 四个安全层次※3. 信息安全保护等级※4. 安全保护能力的等级※ 二、信息加密、解密与常用算法 1. 对称加密2. 非对称加密3. Hash函数4. 数字签名5. 认证 三、信息系统安全 1. 计算机设备安全2. 网络安全3. 操作系统安全4. 数据库安全5. 应用系…...

【数据结构】最小生成树(Prim算法,普里姆算法,普利姆)、最短路径(Dijkstra算法,迪杰斯特拉算法,单源最短路径)

文章目录前置问题问题解答一、基础概念&#xff1a;最小生成树的定义和性质&#xff08;1&#xff09;最小生成树&#xff08;Minimal Spanning Tree&#xff09;的定义&#xff08;2&#xff09;最小生成树&#xff08;MST&#xff09;的性质二、如何利用MST性质寻找最小生成树…...

Session与Cookie的区别(一)

从我刚开始学程序时这一题就常出现在面试考题里&#xff0c;一直到现在都还是能看见这个问题。 这个问题重要吗&#xff1f;我觉得蛮重要的。因为 Session 所代表的是「状态」&#xff0c;如果没有了状态&#xff0c;一大堆功能都会失效。 对于工程师来说必须去理解什么是 Sess…...

【Java】重载和重写的区别

重载(Overload) 在同一个类中&#xff0c;同名的方法如果有不同的参数列表&#xff08;参数类型不同、参数个数不同甚至是参数顺序不同&#xff09;则视为重载。同时&#xff0c;重载对返回类型没有要求&#xff0c;可以相同也可以不同&#xff0c;但不能通过返回类型是否相同…...

AcWing 第 90 场周赛

目录A、首字母大写B、找数字C、构造字符串A、首字母大写 原题链接&#xff1a;AcWing 4806. 首字母大写 签到题。 #include <bits/stdc.h>using namespace std;int main() {ios::sync_with_stdio(false);cin.tie(nullptr);string s;cin >> s;s[0] toupper(s[0]);…...

刚刚,体验了一把Bing chat很爽

文章目录刚刚&#xff0c;体验了一把Bing chat很爽你能做啥&#xff1f;与chatgpt有什么不同&#xff1f;以下是Bingchat的 10个新功能1⃣️在网上搜索结果2⃣️摘要链接3⃣️对话助手4⃣️向您发送实际信息&#xff0c;正确的链接5⃣️在单个查询中执行多个搜索6⃣️玩冒险游戏…...

牛客网Python篇数据分析习题(二)

1.现有一个Nowcoder.csv文件&#xff0c;它记录了牛客网的部分用户数据&#xff0c;包含如下字段&#xff08;字段与字段之间以逗号间隔&#xff09;&#xff1a; Nowcoder_ID&#xff1a;用户ID Level&#xff1a;等级 Achievement_value&#xff1a;成就值 Num_of_exercise&a…...

龙虎榜——20250610

上证指数放量收阴线&#xff0c;个股多数下跌&#xff0c;盘中受消息影响大幅波动。 深证指数放量收阴线形成顶分型&#xff0c;指数短线有调整的需求&#xff0c;大概需要一两天。 2025年6月10日龙虎榜行业方向分析 1. 金融科技 代表标的&#xff1a;御银股份、雄帝科技 驱动…...

网络六边形受到攻击

大家读完觉得有帮助记得关注和点赞&#xff01;&#xff01;&#xff01; 抽象 现代智能交通系统 &#xff08;ITS&#xff09; 的一个关键要求是能够以安全、可靠和匿名的方式从互联车辆和移动设备收集地理参考数据。Nexagon 协议建立在 IETF 定位器/ID 分离协议 &#xff08;…...

19c补丁后oracle属主变化,导致不能识别磁盘组

补丁后服务器重启&#xff0c;数据库再次无法启动 ORA01017: invalid username/password; logon denied Oracle 19c 在打上 19.23 或以上补丁版本后&#xff0c;存在与用户组权限相关的问题。具体表现为&#xff0c;Oracle 实例的运行用户&#xff08;oracle&#xff09;和集…...

JavaScript 中的 ES|QL:利用 Apache Arrow 工具

作者&#xff1a;来自 Elastic Jeffrey Rengifo 学习如何将 ES|QL 与 JavaScript 的 Apache Arrow 客户端工具一起使用。 想获得 Elastic 认证吗&#xff1f;了解下一期 Elasticsearch Engineer 培训的时间吧&#xff01; Elasticsearch 拥有众多新功能&#xff0c;助你为自己…...

【Linux】C语言执行shell指令

在C语言中执行Shell指令 在C语言中&#xff0c;有几种方法可以执行Shell指令&#xff1a; 1. 使用system()函数 这是最简单的方法&#xff0c;包含在stdlib.h头文件中&#xff1a; #include <stdlib.h>int main() {system("ls -l"); // 执行ls -l命令retu…...

【SpringBoot】100、SpringBoot中使用自定义注解+AOP实现参数自动解密

在实际项目中,用户注册、登录、修改密码等操作,都涉及到参数传输安全问题。所以我们需要在前端对账户、密码等敏感信息加密传输,在后端接收到数据后能自动解密。 1、引入依赖 <dependency><groupId>org.springframework.boot</groupId><artifactId...

《Playwright:微软的自动化测试工具详解》

Playwright 简介:声明内容来自网络&#xff0c;将内容拼接整理出来的文档 Playwright 是微软开发的自动化测试工具&#xff0c;支持 Chrome、Firefox、Safari 等主流浏览器&#xff0c;提供多语言 API&#xff08;Python、JavaScript、Java、.NET&#xff09;。它的特点包括&a…...

Cinnamon修改面板小工具图标

Cinnamon开始菜单-CSDN博客 设置模块都是做好的&#xff0c;比GNOME简单得多&#xff01; 在 applet.js 里增加 const Settings imports.ui.settings;this.settings new Settings.AppletSettings(this, HTYMenusonichy, instance_id); this.settings.bind(menu-icon, menu…...

ETLCloud可能遇到的问题有哪些?常见坑位解析

数据集成平台ETLCloud&#xff0c;主要用于支持数据的抽取&#xff08;Extract&#xff09;、转换&#xff08;Transform&#xff09;和加载&#xff08;Load&#xff09;过程。提供了一个简洁直观的界面&#xff0c;以便用户可以在不同的数据源之间轻松地进行数据迁移和转换。…...

c#开发AI模型对话

AI模型 前面已经介绍了一般AI模型本地部署&#xff0c;直接调用现成的模型数据。这里主要讲述讲接口集成到我们自己的程序中使用方式。 微软提供了ML.NET来开发和使用AI模型&#xff0c;但是目前国内可能使用不多&#xff0c;至少实践例子很少看见。开发训练模型就不介绍了&am…...