【20230211】【剑指1】搜索与回溯算法II
树的子结构
递归思维:对称性递归
什么是对称性递归?就是对一个对称的数据结构(这里指二叉树)从整体的对称性思考,把大问题分解成子问题进行递归,即不是单独考虑一部分(比如树的左子树),而是同时考虑对称的两部分(左右子树),从而写出对称性的递归代码。
题型分类:
可以用对称性递归解决的二叉树问题大多是判断性问题(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) 利用数组的indexOf下标属性来查询。 如果找到一个 item,则返回 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(持续集成)指开发人员一天内进行多次合并和提交代码操作,并通过自动化测试,完成构建 CD(持续部署)指每次代码更改都会自动部署到对应环境 CI/CD 结合在一起,可以加快开发团…...

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

【C++】模板初阶STL简介
今天,你内卷了吗? 文章目录一、泛型编程二、函数模板(显示实例化和隐式实例化)1.函数模板格式2.单参数模板3.多参数模板4.模板参数的匹配原则三、类模板(没有推演的时机,统一显示实例化)1.类模…...

备战蓝桥杯第一天【二分查找无bug版】
🌹作者:云小逸 📝个人主页:云小逸的主页 📝Github:云小逸的Github 🤟motto:要敢于一个人默默的面对自己,强大自己才是核心。不要等到什么都没有了,才下定决心去做。种一颗树,最好的时间是十年前…...

Java集合中的Map
MapMap接口键 值 对存储键不能重复,值可以重复Map三个实现类的存储结构HashMap:Hash表链表红黑树结构 线程不安全TreeMap: 底层红黑树实现HashTable:hash表链表红黑树 线程安全HashMapHashMap常用方法HashMap<String,String>…...
【java】springboot项目启动数据加载内存中的三种方法
文章目录一、前言二、加载方式2.1、 第一种:使用PostConstruct注解(properties/yaml文件)。2.2、 第二种:使用Order注解和CommandLineRunner接口。2.3、 第三种:使用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,VCS仿真,Verdi看波形,DC做综合下约束,Primetime做STA,Spyglass做异步时序分析。 VCS全称Verilog Computer Simulation ,VCS是逻辑仿真EDA工具的编译源代码的命令。要用VCS做编译仿…...
信息系统安全技术
一、信息安全的有关概念 1. 属性2. 四个安全层次※3. 信息安全保护等级※4. 安全保护能力的等级※ 二、信息加密、解密与常用算法 1. 对称加密2. 非对称加密3. Hash函数4. 数字签名5. 认证 三、信息系统安全 1. 计算机设备安全2. 网络安全3. 操作系统安全4. 数据库安全5. 应用系…...

【数据结构】最小生成树(Prim算法,普里姆算法,普利姆)、最短路径(Dijkstra算法,迪杰斯特拉算法,单源最短路径)
文章目录前置问题问题解答一、基础概念:最小生成树的定义和性质(1)最小生成树(Minimal Spanning Tree)的定义(2)最小生成树(MST)的性质二、如何利用MST性质寻找最小生成树…...
Session与Cookie的区别(一)
从我刚开始学程序时这一题就常出现在面试考题里,一直到现在都还是能看见这个问题。 这个问题重要吗?我觉得蛮重要的。因为 Session 所代表的是「状态」,如果没有了状态,一大堆功能都会失效。 对于工程师来说必须去理解什么是 Sess…...
【Java】重载和重写的区别
重载(Overload) 在同一个类中,同名的方法如果有不同的参数列表(参数类型不同、参数个数不同甚至是参数顺序不同)则视为重载。同时,重载对返回类型没有要求,可以相同也可以不同,但不能通过返回类型是否相同…...
AcWing 第 90 场周赛
目录A、首字母大写B、找数字C、构造字符串A、首字母大写 原题链接: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很爽
文章目录刚刚,体验了一把Bing chat很爽你能做啥?与chatgpt有什么不同?以下是Bingchat的 10个新功能1⃣️在网上搜索结果2⃣️摘要链接3⃣️对话助手4⃣️向您发送实际信息,正确的链接5⃣️在单个查询中执行多个搜索6⃣️玩冒险游戏…...

牛客网Python篇数据分析习题(二)
1.现有一个Nowcoder.csv文件,它记录了牛客网的部分用户数据,包含如下字段(字段与字段之间以逗号间隔): Nowcoder_ID:用户ID Level:等级 Achievement_value:成就值 Num_of_exercise&a…...
云原生核心技术 (7/12): K8s 核心概念白话解读(上):Pod 和 Deployment 究竟是什么?
大家好,欢迎来到《云原生核心技术》系列的第七篇! 在上一篇,我们成功地使用 Minikube 或 kind 在自己的电脑上搭建起了一个迷你但功能完备的 Kubernetes 集群。现在,我们就像一个拥有了一块崭新数字土地的农场主,是时…...
工程地质软件市场:发展现状、趋势与策略建议
一、引言 在工程建设领域,准确把握地质条件是确保项目顺利推进和安全运营的关键。工程地质软件作为处理、分析、模拟和展示工程地质数据的重要工具,正发挥着日益重要的作用。它凭借强大的数据处理能力、三维建模功能、空间分析工具和可视化展示手段&…...

跨链模式:多链互操作架构与性能扩展方案
跨链模式:多链互操作架构与性能扩展方案 ——构建下一代区块链互联网的技术基石 一、跨链架构的核心范式演进 1. 分层协议栈:模块化解耦设计 现代跨链系统采用分层协议栈实现灵活扩展(H2Cross架构): 适配层…...
vue3 定时器-定义全局方法 vue+ts
1.创建ts文件 路径:src/utils/timer.ts 完整代码: import { onUnmounted } from vuetype TimerCallback (...args: any[]) > voidexport function useGlobalTimer() {const timers: Map<number, NodeJS.Timeout> new Map()// 创建定时器con…...

Linux-07 ubuntu 的 chrome 启动不了
文章目录 问题原因解决步骤一、卸载旧版chrome二、重新安装chorme三、启动不了,报错如下四、启动不了,解决如下 总结 问题原因 在应用中可以看到chrome,但是打不开(说明:原来的ubuntu系统出问题了,这个是备用的硬盘&a…...
精益数据分析(97/126):邮件营销与用户参与度的关键指标优化指南
精益数据分析(97/126):邮件营销与用户参与度的关键指标优化指南 在数字化营销时代,邮件列表效度、用户参与度和网站性能等指标往往决定着创业公司的增长成败。今天,我们将深入解析邮件打开率、网站可用性、页面参与时…...
代理篇12|深入理解 Vite中的Proxy接口代理配置
在前端开发中,常常会遇到 跨域请求接口 的情况。为了解决这个问题,Vite 和 Webpack 都提供了 proxy 代理功能,用于将本地开发请求转发到后端服务器。 什么是代理(proxy)? 代理是在开发过程中,前端项目通过开发服务器,将指定的请求“转发”到真实的后端服务器,从而绕…...

基于SpringBoot在线拍卖系统的设计和实现
摘 要 随着社会的发展,社会的各行各业都在利用信息化时代的优势。计算机的优势和普及使得各种信息系统的开发成为必需。 在线拍卖系统,主要的模块包括管理员;首页、个人中心、用户管理、商品类型管理、拍卖商品管理、历史竞拍管理、竞拍订单…...

基于Springboot+Vue的办公管理系统
角色: 管理员、员工 技术: 后端: SpringBoot, Vue2, MySQL, Mybatis-Plus 前端: Vue2, Element-UI, Axios, Echarts, Vue-Router 核心功能: 该办公管理系统是一个综合性的企业内部管理平台,旨在提升企业运营效率和员工管理水…...

WPF八大法则:告别模态窗口卡顿
⚙️ 核心问题:阻塞式模态窗口的缺陷 原始代码中ShowDialog()会阻塞UI线程,导致后续逻辑无法执行: var result modalWindow.ShowDialog(); // 线程阻塞 ProcessResult(result); // 必须等待窗口关闭根本问题:…...