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

【一刷《剑指Offer》】面试题 18:树的子结构

力扣对应题目链接:LCR 143. 子结构判断 - 力扣(LeetCode)

牛客对应题目链接:树的子结构_牛客题霸_牛客网 (nowcoder.com)

核心考点:二叉树理解,二叉树遍历。 


一、《剑指Offer》对应内容


二、分析问题

二叉树都是递归定义的,所以递归操作是比较常见的做法。
首先明白:子结构怎么理解,可以理解成子结构是原树的子树(或者一部分)。也就是说,B 要是 A 的子结构,那么 B 的根节点+左子树+右子树都得在 A 中存在且构成树形结构。
比较的过程要分为两步:
  1. 先确定比较的起始位置。
  2. 在确定从该位置开始,在比较其左右子树的内容是否一致。

三、代码

//力扣AC代码
/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public:bool hasSubtree(TreeNode* a, TreeNode* b){if(b==NULL) return true;if(a==NULL) return false;if(a->val!=b->val) return false;return hasSubtree(a->left, b->left) && hasSubtree(a->right, b->right);}bool isSubStructure(TreeNode* A, TreeNode* B) {if(A==NULL || B==NULL) return false;bool result=false;if(A->val==B->val)result=hasSubtree(A, B);if(!result)result=isSubStructure(A->left, B);if(!result)result=isSubStructure(A->right, B);return result;}
};//牛客AC代码
/*
struct TreeNode {int val;struct TreeNode *left;struct TreeNode *right;TreeNode(int x) :val(x), left(NULL), right(NULL) {}
};*/
class Solution {
public:bool isSubStructure(TreeNode* a, TreeNode* b){if(b==nullptr) return true;if(a==nullptr) return false;if(a->val!=b->val) return false;return isSubStructure(a->left, b->left) && isSubStructure(a->right, b->right);}bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2) {if(pRoot1==nullptr || pRoot2==nullptr) return false;bool result=false;if(pRoot1->val==pRoot2->val)result=isSubStructure(pRoot1, pRoot2);if(!result)result=HasSubtree(pRoot1->left, pRoot2);if(!result)result=HasSubtree(pRoot1->right, pRoot2);return result;}
};

相关文章:

【一刷《剑指Offer》】面试题 18:树的子结构

力扣对应题目链接:LCR 143. 子结构判断 - 力扣(LeetCode) 牛客对应题目链接:树的子结构_牛客题霸_牛客网 (nowcoder.com) 核心考点:二叉树理解,二叉树遍历。 一、《剑指Offer》对应内容 二、分析问题 二叉…...

17 M-LAG 配置思路

16 华三数据中心最流行的技术 M-LAG-CSDN博客 M-LAG 配置思路 什么是M-LAG?为什么需要M-LAG? - 华为 (huawei.com) 1 配置 M-LAG 的固定的MAC地址 [SW-MLAG]m-lag system-mac 2-2-2 2 配置M-LAG 的系统标识符系统范围1到2 [SW-MLAG]m-lag system-nu…...

深入探索CSS3 appearance 属性:解锁原生控件的定制秘密

CSS3 的 appearance 属性,作为一个强大的工具,让我们得以细致入微地控制元素的外观,特别是对于那些具有平台特定样式的表单元素,如按钮、输入框等。本文不仅会深入解析 appearance 属性的基本工作原理和使用场景,还将通…...

C# 集合(五) —— Dictionary类

总目录 C# 语法总目录 集合五 Dictionary 1. Dictionary 1. Dictionary 字典是键值对集合,通过键值对来查找 Dictionary和Hashtable的区别是Dictionary可以用泛型,而HashTable不能用泛型 OrderedDictionary 是按照添加元素时的顺序的字典,是…...

Java 函数式接口BiConsumer

BiConsumer是一个函数式接口&#xff0c;代表一个接受两个输入参数且不返回任何内容的操作符 import java.util.ArrayList; import java.util.List; import java.util.function.BiConsumer;public class BatchOperate<T> {private int batchSize3000;private List<T&…...

SWERC 2022-2023 - Online Mirror H. Beppa and SwerChat (双指针)

Beppa and SwerChat 题面翻译 B和她的怪胎朋友在某个社交软件上的聊天群聊天。 这个聊天群有包括B在内的n名成员&#xff0c;每个成员都有自己从1-n的独特id。 最近使用这个聊天群的成员将会在列表最上方&#xff0c;接下来较次使用聊天软件的成员将会在列表第二名&#xff0…...

四川汇昌联信:拼多多运营属于什么行业?

拼多多运营属于什么行业?这个问题看似简单&#xff0c;实则涉及到了电商行业的深层次理解。拼多多运营&#xff0c;顾名思义&#xff0c;就是在拼多多这个电商平台上进行商品销售、推广、客户服务等一系列活动。那么&#xff0c;这个行业具体包含哪些内容呢?下面就从四个不同…...

C++11 特性

总结 语法糖: 关键字: auto、decltype。nullptr。override、final。constexpr。语法: 基于范围的 for 循环。function 函数对象。 lambda 产生函数对象。bind 产生函数对象。目的:写代码更便捷、更严谨,让编译器做更多的事情。STL 容器: array。forward_list。unordered_…...

二、使用插件一键安装HybridCLR

预告 本专栏将介绍如何使用这个支持热更的AR开发插件&#xff0c;快速地开发AR应用。 专栏&#xff1a; Unity开发AR系列 插件简介 通过热更技术实现动态地加载AR场景&#xff0c;简化了AR开发流程&#xff0c;让用户可更多地关注Unity场景内容的制作。 热更方案 基于Hybri…...

【江科大STM32学习笔记】新建工程

1.建立工程文件夹&#xff0c;Keil中新建工程&#xff0c;选择型号 2.工程文件夹里建立Start、Library、User等文件夹&#xff0c;复制固件库里面的文件到工程文件夹 为添加工程文件准备&#xff0c;建文件夹是因为文件比较多需要分类管理&#xff0c;需要用到的文件一定要复…...

C++小程序:同一路由器下两台计算机简单通信(1/2)——服务器端

同一路由器下两台电脑如何进行通信呢&#xff1f;这里通过小程序实例的方式介绍SOCKET结构体以及相关函数的使用。计算机通信是在服务器端与客户端之间进行&#xff0c;这里先介绍服务器端程序。 我这里编辑编译软件是VS2022&#xff0c;使用C空项目进行编程。在介绍程序…...

EditReady for Mac激活版:专业视频转码工具

对于视频专业人员来说&#xff0c;一款高效的视频转码工具是不可或缺的。EditReady for Mac正是这样一款强大的工具&#xff0c;它拥有简洁直观的操作界面和强大的功能&#xff0c;让您的视频处理工作事半功倍。 EditReady for Mac支持多种视频格式的转码&#xff0c;并且支持常…...

Android app通过jcifs-ng实现Samba连接共享文件夹

Android端使用Samba连接共享文件夹&#xff0c;下载或上传文件的功能实现。如果你是用jcifs工具包&#xff0c;那么你要注意jcifs-ng 和 jcifs 支持的SMB版本区别。 JCIFS-NG的github地址 JCIFS官网地址 这里有关于jciffs、jcifs-codelibs、jcifs-ng、smbj的详细介绍 对比 支…...

linux开发笔记(buildroot打包镜像)

参考文章:https://www.cnblogs.com/arnoldlu/p/9553995.html mangopi_r3的buildroot在编译完成后会将所有镜像打包到一起。与之有关的buildroot配置项为 BR2_ROOTFS_POST_IMAGE_SCRIPT"board/allwinner/generic/scripts/genimage.sh" genimage.sh内容如下 #!/bin…...

预编码算法学习笔记

预编码算法是无线通信系统中的一项关键技术&#xff0c;它能够在发送端对信号进行处理&#xff0c;以提高系统的可靠性和频谱效率。以下是关于预编码算法的详细学习笔记。 1. 引言 在无线通信系统中&#xff0c;由于存在多径效应、信号衰减以及干扰等因素&#xff0c;接收到的…...

2024OD机试卷-最长子字符串的长度(一) (java\python\c++)

题目:最长子字符串的长度(一) 题目描述 给你一个字符串 s,首尾相连成一个环形,请你在环中找出 ‘o’ 字符出现了偶数次最长 子字符串 的长度。 输入描述 输入是一个小写字母组成的字符串 输出描述 输出是一个整数 用例1 输入 alolobo 输出 6 用例2 输入 looxdolx …...

docker 部署并运行一个微服务

要将微服务部署并运行在Docker容器中&#xff0c;你需要按照以下步骤操作&#xff1a; 编写Dockerfile&#xff1a;在项目根目录下创建一个名为Dockerfile的文件&#xff0c;并添加以下内容&#xff1a; # 使用一个基础的Docker镜像 FROM docker-image# 将项目文件复制到容器…...

Hive on Tez 作业优化参数

常用参数 参数名 参数说明 默认值 所在配置文件 关联问题 hive.tez.container.size Tez AppMaster向RM申请的container大小 -(单位:MB) hive-site.xml OOM tez.runtime.io.sort.mb 这个参数设定了 Tez 运行排序操作时可用的最大内存。排序操作的内存大小也会影响到排序的效率…...

flink mysql数据表同步API CDC

概述&#xff1a; CDC简介 Change Data Capture API CDC同步数据代码 package com.yclxiao.flinkcdcdemo.api;import com.alibaba.fastjson.JSON; import com.alibaba.fastjson.JSONObject; import com.ververica.cdc.connectors.mysql.source.MySqlSource; import com.verv…...

AI大模型探索之路-训练篇21:Llama2微调实战-LoRA技术微调步骤详解

系列篇章&#x1f4a5; AI大模型探索之路-训练篇1&#xff1a;大语言模型微调基础认知 AI大模型探索之路-训练篇2&#xff1a;大语言模型预训练基础认知 AI大模型探索之路-训练篇3&#xff1a;大语言模型全景解读 AI大模型探索之路-训练篇4&#xff1a;大语言模型训练数据集概…...

后进先出(LIFO)详解

LIFO 是 Last In, First Out 的缩写&#xff0c;中文译为后进先出。这是一种数据结构的工作原则&#xff0c;类似于一摞盘子或一叠书本&#xff1a; 最后放进去的元素最先出来 -想象往筒状容器里放盘子&#xff1a; &#xff08;1&#xff09;你放进的最后一个盘子&#xff08…...

UE5 学习系列(二)用户操作界面及介绍

这篇博客是 UE5 学习系列博客的第二篇&#xff0c;在第一篇的基础上展开这篇内容。博客参考的 B 站视频资料和第一篇的链接如下&#xff1a; 【Note】&#xff1a;如果你已经完成安装等操作&#xff0c;可以只执行第一篇博客中 2. 新建一个空白游戏项目 章节操作&#xff0c;重…...

PHP和Node.js哪个更爽?

先说结论&#xff0c;rust完胜。 php&#xff1a;laravel&#xff0c;swoole&#xff0c;webman&#xff0c;最开始在苏宁的时候写了几年php&#xff0c;当时觉得php真的是世界上最好的语言&#xff0c;因为当初活在舒适圈里&#xff0c;不愿意跳出来&#xff0c;就好比当初活在…...

【力扣数据库知识手册笔记】索引

索引 索引的优缺点 优点1. 通过创建唯一性索引&#xff0c;可以保证数据库表中每一行数据的唯一性。2. 可以加快数据的检索速度&#xff08;创建索引的主要原因&#xff09;。3. 可以加速表和表之间的连接&#xff0c;实现数据的参考完整性。4. 可以在查询过程中&#xff0c;…...

ESP32读取DHT11温湿度数据

芯片&#xff1a;ESP32 环境&#xff1a;Arduino 一、安装DHT11传感器库 红框的库&#xff0c;别安装错了 二、代码 注意&#xff0c;DATA口要连接在D15上 #include "DHT.h" // 包含DHT库#define DHTPIN 15 // 定义DHT11数据引脚连接到ESP32的GPIO15 #define D…...

EtherNet/IP转DeviceNet协议网关详解

一&#xff0c;设备主要功能 疆鸿智能JH-DVN-EIP本产品是自主研发的一款EtherNet/IP从站功能的通讯网关。该产品主要功能是连接DeviceNet总线和EtherNet/IP网络&#xff0c;本网关连接到EtherNet/IP总线中做为从站使用&#xff0c;连接到DeviceNet总线中做为从站使用。 在自动…...

微信小程序云开发平台MySQL的连接方式

注&#xff1a;微信小程序云开发平台指的是腾讯云开发 先给结论&#xff1a;微信小程序云开发平台的MySQL&#xff0c;无法通过获取数据库连接信息的方式进行连接&#xff0c;连接只能通过云开发的SDK连接&#xff0c;具体要参考官方文档&#xff1a; 为什么&#xff1f; 因为…...

css3笔记 (1) 自用

outline: none 用于移除元素获得焦点时默认的轮廓线 broder:0 用于移除边框 font-size&#xff1a;0 用于设置字体不显示 list-style: none 消除<li> 标签默认样式 margin: xx auto 版心居中 width:100% 通栏 vertical-align 作用于行内元素 / 表格单元格&#xff…...

蓝桥杯3498 01串的熵

问题描述 对于一个长度为 23333333的 01 串, 如果其信息熵为 11625907.5798&#xff0c; 且 0 出现次数比 1 少, 那么这个 01 串中 0 出现了多少次? #include<iostream> #include<cmath> using namespace std;int n 23333333;int main() {//枚举 0 出现的次数//因…...

Go 语言并发编程基础:无缓冲与有缓冲通道

在上一章节中&#xff0c;我们了解了 Channel 的基本用法。本章将重点分析 Go 中通道的两种类型 —— 无缓冲通道与有缓冲通道&#xff0c;它们在并发编程中各具特点和应用场景。 一、通道的基本分类 类型定义形式特点无缓冲通道make(chan T)发送和接收都必须准备好&#xff0…...