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

二叉树专题

Leetcode 104. 二叉树的最大深度

class Solution {
public:int maxDepth(TreeNode* root) {if(!root)   return 0;int leftd = maxDepth(root -> left) + 1;int rightd= maxDepth(root -> right) + 1;return max(leftd, rightd);}
};

Leetcode 100. 相同的树

class Solution {
public:bool isSameTree(TreeNode* p, TreeNode* q) {if(p && q == nullptr || q && p == nullptr)  return false;if(p == nullptr && q == nullptr)            return true;if(p -> val != q -> val)    return false;bool left = isSameTree(p -> left, q -> left);bool right = isSameTree(p -> right, q ->right);return left && right;}
};

Leetcode 572. 另一棵树的子树

方法一:暴力匹配

上一题问题的延伸,主要注意下什么时候用isSubtree什么时候用isSametree就可以。

class Solution {
public:bool isSametree(TreeNode* a, TreeNode* b){if(a == nullptr && b || a && b == nullptr)  return false;if(a == nullptr && b == nullptr)            return true;if(a -> val != b -> val)                    return false;return isSametree(a -> left, b -> left) && isSametree(a -> right, b -> right);}bool isSubtree(TreeNode* root, TreeNode* subRoot) {if(root && subRoot == nullptr || root == nullptr && subRoot)    return false;if(root -> val != subRoot -> val)return isSubtree(root -> left, subRoot) || isSubtree(root -> right, subRoot);return isSametree(root, subRoot) || isSubtree(root -> left, subRoot) || isSubtree(root -> right, subRoot);}
};

方法二:只在高度相同时匹配

class Solution {
public:int getHeight(TreeNode* root){if(root == nullptr)     return 0;return max(getHeight(root -> left), getHeight(root -> right)) + 1; }bool isSametree(TreeNode* a, TreeNode* b){if(a == nullptr && b || a && b == nullptr)  return false;if(a == nullptr && b == nullptr)            return true;if(a -> val != b -> val)                    return false;return isSametree(a -> left, b -> left) && isSametree(a -> right, b -> right);}bool isSubtree(TreeNode* root, TreeNode* subRoot) { // 只在相同高度才进行比较int hs = getHeight(subRoot);function<pair<int, bool>(TreeNode*)>  dfs = [&](TreeNode* r)->pair<int, bool>{  // 返回pair类型<结点高度,是否与subRoot相同>if (nullptr == r)   return {0, false};    // 高度为0,不是相同子树auto [l_h, l_fg] = dfs(r -> left);auto [r_h, r_fg] = dfs(r -> right);if (l_fg || r_fg)   return {0, true};        // 至少一个存在即可int cur_h = max(l_h, r_h) + 1;return {cur_h, cur_h == hs && isSametree(r, subRoot)};  // 相等的时候再去比较}; return dfs(root).second;}
};

 

相关文章:

二叉树专题

Leetcode 104. 二叉树的最大深度 class Solution { public:int maxDepth(TreeNode* root) {if(!root) return 0;int leftd maxDepth(root -> left) 1;int rightd maxDepth(root -> right) 1;return max(leftd, rightd);} }; Leetcode 100. 相同的树 class Solution…...

Spring MVC 之简介及常见注解

一、什么是 Spring MVC Spring Web MVC 是基于 Servlet API 构建的原始 Web 框架&#xff0c;从一开始就包含在 Spring 框架中。它的正式名称 “Spring Web MVC” 来自其源模块的名称 (Spring-webmvc)&#xff0c;但它通常被称为"Spring MVC"。 什么是Servlet呢? S…...

除了使用本地存储,还有哪些方法可以实现只出现一次的弹窗?

除了使用本地存储&#xff0c;还有以下几种方法可以实现只出现一次的弹窗&#xff1a; 1.使用 Cookie&#xff1a;可以将一个标识符存储在浏览器 Cookie 中&#xff0c;下次用户访问页面时检查 Cookie 中是否存在该标识符&#xff0c;从而判断是否需要显示弹窗。 2.使用服务器端…...

微软蓝屏事件揭示的网络安全深层问题与未来应对策略

目录 微软蓝屏事件揭示的网络安全深层问题与未来应对策略 一、事件背景 二、事件影响 2.1、跨行业连锁反应 2.2、经济损失和社会混乱 三、揭示的网络安全问题 3.2、软件更新管理与风险评估 3.2、系统复杂性与依赖关系 3.3、网络安全意识与培训 四、未来的网络安全方向…...

C#:通用方法总结—第11集

大家好&#xff0c;今天继续分享我们的通用方法系列。 下面是今天要分享的通用方法&#xff1a; &#xff08;1&#xff09;这个通用方法为Ug’校验选中体的个数&#xff1a; /// <summary> /// 输出选中体个数 /// </summary> public int CheckOneBody() { int …...

Web开发-html篇-下

这篇是接着上篇的内容&#xff0c;接着介绍html的其他标签及属性的用法&#xff0c;感兴趣的可以从我的html上篇看起 1. 超链接示例 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><meta name"viewport&…...

【C++从小白到大牛】多态那些事儿(上)

一、多态的概念 1.1概念: 通俗来说&#xff0c;就是多种形态&#xff0c;具体点就是去完成某个行为&#xff0c;当不同的对象去完成时会产生出不同的状态。 二、 多态的定义及实现 2.1多态的构成条件 多态是在不同继承关系的类对象&#xff0c;去调用同一函数&#xff0c;产…...

网站在线查询工具箱源码分享

终极网络工具系统”(SAAS)&#xff0c;是一款功能强大的PHP脚本在线查询工具。本版集合了超过470种快速且易用的Web工具&#xff0c;为日常任务处理和开发人员提供了极大的便利。作为一款综合性的网络工具系统&#xff0c;66toolkit不仅满足了用户的基本网络需求&#xff0c;更…...

SSH简写且免密登陆终端设备

问题 通常使用ssh连接远程设备时&#xff0c;需要先执行ssh <username><ip>&#xff0c;然后再输入终端设备的用户密码。比较麻烦。 解决 可以用如下方法设置命令缩写以及免密登陆&#xff1a; 免密 首先在本地生成私钥&#xff1a; ssh-keygen -t rsa # or …...

算力共享中神经网络切片和算力分配策略

目录 神经网络切片 按照算力的分布进行网络层数切片;就是算力越强,运算神经网络层数越多 神经网络切片和算力占比进行映射 算力分配策略 get_current_shard 神经网络切片 按照算力的分布进行网络层数切片;就是算力越强,运算神经网络层数越多 神经网络切片和算力占比进…...

3章4节:R的逻辑运算和矩阵运算

逻辑运算和矩阵运算是R语言中两个重要的功能模块,前者用于逻辑判断和条件筛选,后者用于处理多维数据结构和执行线性代数运算。本文章详细介绍R语言中的逻辑运算和矩阵运算,帮助读者掌握这两类运算的基本概念、操作方法和实际应用。 一、逻辑运算 逻辑运算在编程语言中扮演着…...

使用EasyAR打包安卓操作注意

EasyAR for Scene 4.6.3 丨Unity2020.3.15f2 打包Unity注意事项 一、默认渲染管线 官方参考链接&#xff1a;ARFoundation 简单注意 1.打包设置为Android平台 2.PackageName和EasyAR中保持一致 3.Scripting Backend设置为IL2CPP&#xff0c;以及设置为ARM64 4.取消Auto …...

驾驭PyCharm:破解环境配置的迷宫

驾驭PyCharm&#xff1a;破解环境配置的迷宫 PyCharm&#xff0c;作为Python开发者的首选IDE之一&#xff0c;以其强大的功能和用户友好的界面而广受好评。然而&#xff0c;即便是最强大的工具&#xff0c;环境配置问题也可能成为开发者的拦路虎。本文将带你深入探索PyCharm中…...

大数据技术原理-Hadoop的安装

摘要 随着大数据时代的到来&#xff0c;Hadoop作为一项重要的分布式计算框架&#xff0c;其安装与配置是大数据技术学习者必须掌握的技能。本文通过实验报告的形式&#xff0c;详细记录了在虚拟机环境下安装Hadoop并配置其为伪分布式模式的全过程。实验过程中&#xff0c;遇到…...

从根儿上学习spring 八 之run方法启动第四段(2)

图2 我们接着上一篇接着来看refresh方法&#xff0c;我们上一小节说完了invokeBeanFactoryPostProcessors(beanFactory)方法&#xff0c;这一节我们来看registerBeanPostProcessors(beanFactory)方法。 从方法名称定义我们就能看出这个方法主要是用来注册BeanPostProcesor的。…...

牛顿插值法代替泰勒公式

引入 例题 近似函数&#xff1a; 通过这个近似函数可以看出&#xff0c;若要证的函数超过二阶可导&#xff0c;那么就不适合用牛顿插值法代替泰勒公式 因为&#xff0c;后面的操作非常复杂&#xff0c;不划算了… 总结 我们可以通过牛顿插值法生成一个逼近曲线的直线&#xf…...

为 Laravel 提供生产模式下的容器化环境:打造现代开发环境的终极指南

为 Laravel 提供生产模式下的容器化环境&#xff1a;打造现代开发环境的终极指南 在现代开发中&#xff0c;容器化已经成为一种趋势。使用 Docker 可以让我们轻松地管理和部署应用程序。本文将带你一步步构建一个高效的 Laravel 容器化环境&#xff0c;确保你的应用程序在开发…...

Visual Studio 和 VSCode 哪个好?

​ 您好&#xff0c;我是程序员小羊&#xff01; 前言 想要对Visual Studio 和 VSCode 进行比较&#xff0c;就要充分了解Visual Studio (VS) 和 Visual Studio Code (VSCode) 各有其优势和适用场景进行分析。Visual Studio (VS) 和 Visual Studio Code (VSCode) 都是由微软开发…...

百款精选的HTML5小游戏源码,你可以下载并直接运行在你的小程序或者自己的网站上

今天我带来了一份特别的礼物——百款精选的HTML5小游戏源码&#xff0c;你可以下载并直接运行在你的小程序或者自己的网站上&#xff0c;只需双击index.html即可开始。无论你是在寻找创意引流&#xff0c;还是想为你的网站增添互动性&#xff0c;这些小游戏都能帮你实现&#x…...

01 LVS负载均衡群集

集群 在互联网应用中&#xff0c;随着站点对硬件的性能、响应速度、服务稳定性、数据可靠性等要求越来越高&#xff0c;单台服务器越来越力不从心 集群的含义 Cluster&#xff0c;集群也叫群集由多台主机构成&#xff0c;但对外只表现为一个整体 集群分类 类型 负载均衡集…...

Linux 文件类型,目录与路径,文件与目录管理

文件类型 后面的字符表示文件类型标志 普通文件&#xff1a;-&#xff08;纯文本文件&#xff0c;二进制文件&#xff0c;数据格式文件&#xff09; 如文本文件、图片、程序文件等。 目录文件&#xff1a;d&#xff08;directory&#xff09; 用来存放其他文件或子目录。 设备…...

以下是对华为 HarmonyOS NETX 5属性动画(ArkTS)文档的结构化整理,通过层级标题、表格和代码块提升可读性:

一、属性动画概述NETX 作用&#xff1a;实现组件通用属性的渐变过渡效果&#xff0c;提升用户体验。支持属性&#xff1a;width、height、backgroundColor、opacity、scale、rotate、translate等。注意事项&#xff1a; 布局类属性&#xff08;如宽高&#xff09;变化时&#…...

2021-03-15 iview一些问题

1.iview 在使用tree组件时&#xff0c;发现没有set类的方法&#xff0c;只有get&#xff0c;那么要改变tree值&#xff0c;只能遍历treeData&#xff0c;递归修改treeData的checked&#xff0c;发现无法更改&#xff0c;原因在于check模式下&#xff0c;子元素的勾选状态跟父节…...

论文浅尝 | 基于判别指令微调生成式大语言模型的知识图谱补全方法(ISWC2024)

笔记整理&#xff1a;刘治强&#xff0c;浙江大学硕士生&#xff0c;研究方向为知识图谱表示学习&#xff0c;大语言模型 论文链接&#xff1a;http://arxiv.org/abs/2407.16127 发表会议&#xff1a;ISWC 2024 1. 动机 传统的知识图谱补全&#xff08;KGC&#xff09;模型通过…...

C++中string流知识详解和示例

一、概览与类体系 C 提供三种基于内存字符串的流&#xff0c;定义在 <sstream> 中&#xff1a; std::istringstream&#xff1a;输入流&#xff0c;从已有字符串中读取并解析。std::ostringstream&#xff1a;输出流&#xff0c;向内部缓冲区写入内容&#xff0c;最终取…...

大模型多显卡多服务器并行计算方法与实践指南

一、分布式训练概述 大规模语言模型的训练通常需要分布式计算技术,以解决单机资源不足的问题。分布式训练主要分为两种模式: 数据并行:将数据分片到不同设备,每个设备拥有完整的模型副本 模型并行:将模型分割到不同设备,每个设备处理部分模型计算 现代大模型训练通常结合…...

【Java_EE】Spring MVC

目录 Spring Web MVC ​编辑注解 RestController RequestMapping RequestParam RequestParam RequestBody PathVariable RequestPart 参数传递 注意事项 ​编辑参数重命名 RequestParam ​编辑​编辑传递集合 RequestParam 传递JSON数据 ​编辑RequestBody ​…...

【JavaWeb】Docker项目部署

引言 之前学习了Linux操作系统的常见命令&#xff0c;在Linux上安装软件&#xff0c;以及如何在Linux上部署一个单体项目&#xff0c;大多数同学都会有相同的感受&#xff0c;那就是麻烦。 核心体现在三点&#xff1a; 命令太多了&#xff0c;记不住 软件安装包名字复杂&…...

以光量子为例,详解量子获取方式

光量子技术获取量子比特可在室温下进行。该方式有望通过与名为硅光子学&#xff08;silicon photonics&#xff09;的光波导&#xff08;optical waveguide&#xff09;芯片制造技术和光纤等光通信技术相结合来实现量子计算机。量子力学中&#xff0c;光既是波又是粒子。光子本…...

纯 Java 项目(非 SpringBoot)集成 Mybatis-Plus 和 Mybatis-Plus-Join

纯 Java 项目&#xff08;非 SpringBoot&#xff09;集成 Mybatis-Plus 和 Mybatis-Plus-Join 1、依赖1.1、依赖版本1.2、pom.xml 2、代码2.1、SqlSession 构造器2.2、MybatisPlus代码生成器2.3、获取 config.yml 配置2.3.1、config.yml2.3.2、项目配置类 2.4、ftl 模板2.4.1、…...