当前位置: 首页 > 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…...

云原生核心技术 (7/12): K8s 核心概念白话解读(上):Pod 和 Deployment 究竟是什么?

大家好&#xff0c;欢迎来到《云原生核心技术》系列的第七篇&#xff01; 在上一篇&#xff0c;我们成功地使用 Minikube 或 kind 在自己的电脑上搭建起了一个迷你但功能完备的 Kubernetes 集群。现在&#xff0c;我们就像一个拥有了一块崭新数字土地的农场主&#xff0c;是时…...

工程地质软件市场:发展现状、趋势与策略建议

一、引言 在工程建设领域&#xff0c;准确把握地质条件是确保项目顺利推进和安全运营的关键。工程地质软件作为处理、分析、模拟和展示工程地质数据的重要工具&#xff0c;正发挥着日益重要的作用。它凭借强大的数据处理能力、三维建模功能、空间分析工具和可视化展示手段&…...

跨链模式:多链互操作架构与性能扩展方案

跨链模式&#xff1a;多链互操作架构与性能扩展方案 ——构建下一代区块链互联网的技术基石 一、跨链架构的核心范式演进 1. 分层协议栈&#xff1a;模块化解耦设计 现代跨链系统采用分层协议栈实现灵活扩展&#xff08;H2Cross架构&#xff09;&#xff1a; 适配层&#xf…...

vue3 定时器-定义全局方法 vue+ts

1.创建ts文件 路径&#xff1a;src/utils/timer.ts 完整代码&#xff1a; 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三、启动不了&#xff0c;报错如下四、启动不了&#xff0c;解决如下 总结 问题原因 在应用中可以看到chrome&#xff0c;但是打不开(说明&#xff1a;原来的ubuntu系统出问题了&#xff0c;这个是备用的硬盘&a…...

精益数据分析(97/126):邮件营销与用户参与度的关键指标优化指南

精益数据分析&#xff08;97/126&#xff09;&#xff1a;邮件营销与用户参与度的关键指标优化指南 在数字化营销时代&#xff0c;邮件列表效度、用户参与度和网站性能等指标往往决定着创业公司的增长成败。今天&#xff0c;我们将深入解析邮件打开率、网站可用性、页面参与时…...

代理篇12|深入理解 Vite中的Proxy接口代理配置

在前端开发中,常常会遇到 跨域请求接口 的情况。为了解决这个问题,Vite 和 Webpack 都提供了 proxy 代理功能,用于将本地开发请求转发到后端服务器。 什么是代理(proxy)? 代理是在开发过程中,前端项目通过开发服务器,将指定的请求“转发”到真实的后端服务器,从而绕…...

基于SpringBoot在线拍卖系统的设计和实现

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

基于Springboot+Vue的办公管理系统

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

WPF八大法则:告别模态窗口卡顿

⚙️ 核心问题&#xff1a;阻塞式模态窗口的缺陷 原始代码中ShowDialog()会阻塞UI线程&#xff0c;导致后续逻辑无法执行&#xff1a; var result modalWindow.ShowDialog(); // 线程阻塞 ProcessResult(result); // 必须等待窗口关闭根本问题&#xff1a…...