当前位置: 首页 > 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;但对外只表现为一个整体 集群分类 类型 负载均衡集…...

C++实现分布式网络通信框架RPC(3)--rpc调用端

目录 一、前言 二、UserServiceRpc_Stub 三、 CallMethod方法的重写 头文件 实现 四、rpc调用端的调用 实现 五、 google::protobuf::RpcController *controller 头文件 实现 六、总结 一、前言 在前边的文章中&#xff0c;我们已经大致实现了rpc服务端的各项功能代…...

【OSG学习笔记】Day 18: 碰撞检测与物理交互

物理引擎&#xff08;Physics Engine&#xff09; 物理引擎 是一种通过计算机模拟物理规律&#xff08;如力学、碰撞、重力、流体动力学等&#xff09;的软件工具或库。 它的核心目标是在虚拟环境中逼真地模拟物体的运动和交互&#xff0c;广泛应用于 游戏开发、动画制作、虚…...

Debian系统简介

目录 Debian系统介绍 Debian版本介绍 Debian软件源介绍 软件包管理工具dpkg dpkg核心指令详解 安装软件包 卸载软件包 查询软件包状态 验证软件包完整性 手动处理依赖关系 dpkg vs apt Debian系统介绍 Debian 和 Ubuntu 都是基于 Debian内核 的 Linux 发行版&#xff…...

uni-app学习笔记二十二---使用vite.config.js全局导入常用依赖

在前面的练习中&#xff0c;每个页面需要使用ref&#xff0c;onShow等生命周期钩子函数时都需要像下面这样导入 import {onMounted, ref} from "vue" 如果不想每个页面都导入&#xff0c;需要使用node.js命令npm安装unplugin-auto-import npm install unplugin-au…...

解锁数据库简洁之道:FastAPI与SQLModel实战指南

在构建现代Web应用程序时&#xff0c;与数据库的交互无疑是核心环节。虽然传统的数据库操作方式&#xff08;如直接编写SQL语句与psycopg2交互&#xff09;赋予了我们精细的控制权&#xff0c;但在面对日益复杂的业务逻辑和快速迭代的需求时&#xff0c;这种方式的开发效率和可…...

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

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

Device Mapper 机制

Device Mapper 机制详解 Device Mapper&#xff08;简称 DM&#xff09;是 Linux 内核中的一套通用块设备映射框架&#xff0c;为 LVM、加密磁盘、RAID 等提供底层支持。本文将详细介绍 Device Mapper 的原理、实现、内核配置、常用工具、操作测试流程&#xff0c;并配以详细的…...

使用LangGraph和LangSmith构建多智能体人工智能系统

现在&#xff0c;通过组合几个较小的子智能体来创建一个强大的人工智能智能体正成为一种趋势。但这也带来了一些挑战&#xff0c;比如减少幻觉、管理对话流程、在测试期间留意智能体的工作方式、允许人工介入以及评估其性能。你需要进行大量的反复试验。 在这篇博客〔原作者&a…...

力扣热题100 k个一组反转链表题解

题目: 代码: func reverseKGroup(head *ListNode, k int) *ListNode {cur : headfor i : 0; i < k; i {if cur nil {return head}cur cur.Next}newHead : reverse(head, cur)head.Next reverseKGroup(cur, k)return newHead }func reverse(start, end *ListNode) *ListN…...

OD 算法题 B卷【正整数到Excel编号之间的转换】

文章目录 正整数到Excel编号之间的转换 正整数到Excel编号之间的转换 excel的列编号是这样的&#xff1a;a b c … z aa ab ac… az ba bb bc…yz za zb zc …zz aaa aab aac…; 分别代表以下的编号1 2 3 … 26 27 28 29… 52 53 54 55… 676 677 678 679 … 702 703 704 705;…...