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

想要精通算法和SQL的成长之路 - 二叉树的判断问题(子树判断 | 对称性 | 一致性判断)

想要精通算法和SQL的成长之路 - 二叉树的判断问题

  • 前言
  • 一. 相同的树
  • 二. 对称二叉树
  • 三. 判断子树

前言

想要精通算法和SQL的成长之路 - 系列导航

一. 相同的树

原题链接
在这里插入图片描述

这题目典型的递归题:

  • 如果两个节点都是null,我们返回true
  • 如果两个节点一个null,一个非空,返回false
  • 最后满足条件:当前两个节点值相等,并且两个节点的左子树相等,右子树也相等。

代码如下:

public boolean isSameTree(TreeNode p, TreeNode q) {if (p == null && q == null) {return true;}if (p == null || q == null) {return false;}return p.val == q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}

二. 对称二叉树

原题链接
在这里插入图片描述
这个题目,我们依旧使用递归算法。我们可以在第一题的基础上,做一个改变。
一致性代码:

return p.val == q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right);

对称代码:

return p.val == q.val && isSameTree(p.left, q.right) && isSameTree(p.right, q.left);

最终完整代码如下:

public boolean isSymmetric(TreeNode root) {return helper(root.left, root.right);
}public boolean helper(TreeNode p, TreeNode q) {if (p == null && q == null) {return true;}if (p == null || q == null) {return false;}return p.val == q.val && helper(p.left, q.right) && helper(p.right, q.left);
}

三. 判断子树

原题链接
在这里插入图片描述
此题依旧是第一题的一个进阶版,判断B是否是A的子树可以等同于:

  • AB 是否相同?
  • A.leftB 是否相同?
  • A.rightB 是否相同?
  • 以此类推…

那么在第一题的基础上,我们有了函数去判断两棵树是否相等,我们只需要完成上面的判断即可:

public boolean isSubtree(TreeNode root, TreeNode subRoot) {// 特判:root肯定不能为nullif (root == null) {return false;}// 特判:subRoot子树允许为nullif (subRoot == null) {return true;}return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot) || isSameTree(root, subRoot);
}public boolean isSameTree(TreeNode p, TreeNode q) {if (p == null && q == null) {return true;}if (p == null || q == null) {return false;}if (p.val != q.val) {return false;}return p.val == q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}

相关文章:

想要精通算法和SQL的成长之路 - 二叉树的判断问题(子树判断 | 对称性 | 一致性判断)

想要精通算法和SQL的成长之路 - 二叉树的判断问题 前言一. 相同的树二. 对称二叉树三. 判断子树 前言 想要精通算法和SQL的成长之路 - 系列导航 一. 相同的树 原题链接 这题目典型的递归题: 如果两个节点都是null,我们返回true。如果两个节点一个nul…...

(零)如何做机器视觉项目

文章目录 1 项目的前期准备1.1 从5个方面初步分析客户需求1.2 方案评估与验证1.3 签订合同 2 项目规划2.1 定义客户端的详细需求2.2 制定项目管理计划2.3 方案评审 3 详细设计3.1 硬件设备的选择与环境搭建3.2 软件开发平台与开发工具的选择3.3 机器视觉系统的整体框架与开发流…...

【Leetcode】滑动窗口合集

这里写目录标题 209.长度最小的子数组题目思路代码 3. 无重复字符的最长子串(medium)题目思路 11. 最大连续 1 的个数 III题目思路 1658. 将 x 减到 0 的最⼩操作数题目思路代码 904. 水果成篮题目思路代码 438.找到字符串中所有字母的异位词题目思路代码…...

【C++】STL详解(九)—— set、map、multiset、multimap的介绍及使用

​ ​📝个人主页:Sherry的成长之路 🏠学习社区:Sherry的成长之路(个人社区) 📖专栏链接:C学习 🎯长路漫漫浩浩,万事皆有期待 上一篇博客:【C】STL…...

计组—— I/O系统

📕:参考王道课件 目录 一、I/O系统的基本概念 1.什么是“I/O”? ​编辑2.主机如何和I/O设备进行交互? 3.I/O控制方式 (1)程序查询方式 (2)程序中断方式 (3&#x…...

基于vc6+sdk51开发简易文字识别转语音的程序

系统:window7 软件:vc6.0 目的:简易文字转语音真人发声 利用2023国庆小长假,研究如何将文言转语音,之前在网上查询相关知识,大致了解微信语音转换,翻译官之类软件的原理,但要加入神…...

DevOps:自动化部署和持续集成/持续交付(CI/CD)

DevOps:自动化部署和持续集成/持续交付(CI/CD) 在现代软件开发领域,DevOps(Development和Operations的组合)已经成为一个不可或缺的概念。它代表了一种将软件开发和运维(Operations&#xff09…...

专业图标制作软件 Image2icon 最新中文 for mac

Image2Icon是一款用于Mac操作系统的图标转换工具。它允许用户将常见的图像文件(如PNG、JPEG、GIF等)转换为图标文件(.ico格式),以便在Mac上用作应用程序、文件夹或驱动器的自定义图标。 以下是Image2Icon的一些主要功…...

数据结构:顺序表

SeqList.h #pragma once #include<stdio.h> #include<assert.h> #include<stdlib.h>typedef int SLDataType; //#define NULL 0typedef struct SeqList {SLDataType* a;int size;//顺序表中存储的有效元素的个数int capacity;//空间的大小 }SL;void SLInit(…...

僵尸进程的产生与处理

僵尸进程&#xff08;Zombie Process&#xff09;是指在操作系统中已经完成了执行&#xff0c;但其父进程尚未调用wait()或waitpid()来获取其终止状态的子进程。当一个进程结束时&#xff0c;操作系统会保留该进程的一些基本信息&#xff0c;包括进程ID&#xff08;PID&#xf…...

TouchEffects - Android View点击特效

官网 GitHub - likaiyuan559/TouchEffects: Android View点击特效TouchEffects,几行代码为所有控件添加点击效果 项目简介 Android View点击特效TouchEffects,几行代码为所有控件添加点击效果 TouchEffects能够帮助你更快速方便的增加点击时候的效果&#xff0c;TouchEffect…...

从ContinuousEventTimeTrigger/ContinuousProcessingTimeTrigger代码看如何实现一个自定义的触发器

背景 当我们想要实现提前触发计算的触发器时&#xff0c;我们可以使用ContinuousEventTimeTrigger/ContinuousProcessingTimeTrigger作为触发器达到比如几分钟触发一次计算并发送计算结果的类&#xff0c;我们本文就从代码角度解析下实现自定义触发器的一些注意事项 Continuo…...

Linux 5种网络模型

[参考]&#xff1a;《黑马程序员Redis》https://www.bilibili.com/video/BV1cr4y1671t/?p166&share_sourcecopy_web&vd_source9e65300ccca322aeb367bb1eb677b0fc [参考]&#xff1a;《操作系统》 [参考]&#xff1a;《UNIX网络编程》 为了避免用户应用导致冲突甚至内…...

10.1 调试事件读取寄存器

当读者需要获取到特定进程内的寄存器信息时&#xff0c;则需要在上述代码中进行完善&#xff0c;首先需要编写CREATE_PROCESS_DEBUG_EVENT事件&#xff0c;程序被首次加载进入内存时会被触发此事件&#xff0c;在该事件内首先我们通过lpStartAddress属性获取到当前程序的入口地…...

Linux系统常用指令篇---(一)

Linux系统常用指令篇—(一) 1.cd指令 Linux系统中&#xff0c;磁盘上的文件和目录被组成一棵目录树&#xff0c;每个节点都是目录或文件。 语法:cd 目录名 功能&#xff1a;改变工作目录。将当前工作目录改变到指定的目录下。 (简单理解为进入指定目录下) 举例: cd .. : 返…...

【初识Linux】:常见指令(1)

朋友们、伙计们&#xff0c;我们又见面了&#xff0c;本期来给大家解读一下有关Linux的基础知识点&#xff0c;如果看完之后对你有一定的启发&#xff0c;那么请留下你的三连&#xff0c;祝大家心想事成&#xff01; C 语 言 专 栏&#xff1a;C语言&#xff1a;从入门到精通 数…...

STM32复习笔记(四):看门狗

目录 &#xff08;一&#xff09;简介 &#xff08;二&#xff09;IWDG IWDG的CUBEMX工程配置 IWDG相关函数&#xff08;非常少&#xff0c;所以直接贴上来&#xff09;&#xff1a; &#xff08;三&#xff09;WWDG &#xff08;一&#xff09;简介 看门狗分为独立看门…...

【C++进阶(七)】仿函数深度剖析模板进阶讲解

&#x1f493;博主CSDN主页:杭电码农-NEO&#x1f493;   ⏩专栏分类:C从入门到精通⏪   &#x1f69a;代码仓库:NEO的学习日记&#x1f69a;   &#x1f339;关注我&#x1faf5;带你学习C   &#x1f51d;&#x1f51d; 模板进阶 1. 前言2. 仿函数的概念3. 仿函数的实…...

基于SSM的电动车上牌管理系统(有报告)。Javaee项目。

演示视频&#xff1a; 基于SSM的电动车上牌管理系统&#xff08;有报告&#xff09;。Javaee项目。 项目介绍&#xff1a; 采用M&#xff08;model&#xff09;V&#xff08;view&#xff09;C&#xff08;controller&#xff09;三层体系结构&#xff0c;通过Spring SpringM…...

mstsc无法保存RDP凭据, 100%生效

问题 即使如下两项都打勾&#xff0c;其还是无法保存凭据&#xff0c;特别是连接Ubuntu (freerdp server)&#xff1a; 解决方法 网上多种复杂方法&#xff0c;不生效&#xff0c;其思路是修改后台配置&#xff0c;以使mstsc跟平常一样自动记住凭据。最后&#xff0c;如下的…...

国防科技大学计算机基础课程笔记02信息编码

1.机内码和国标码 国标码就是我们非常熟悉的这个GB2312,但是因为都是16进制&#xff0c;因此这个了16进制的数据既可以翻译成为这个机器码&#xff0c;也可以翻译成为这个国标码&#xff0c;所以这个时候很容易会出现这个歧义的情况&#xff1b; 因此&#xff0c;我们的这个国…...

从零实现富文本编辑器#5-编辑器选区模型的状态结构表达

先前我们总结了浏览器选区模型的交互策略&#xff0c;并且实现了基本的选区操作&#xff0c;还调研了自绘选区的实现。那么相对的&#xff0c;我们还需要设计编辑器的选区表达&#xff0c;也可以称为模型选区。编辑器中应用变更时的操作范围&#xff0c;就是以模型选区为基准来…...

中南大学无人机智能体的全面评估!BEDI:用于评估无人机上具身智能体的综合性基准测试

作者&#xff1a;Mingning Guo, Mengwei Wu, Jiarun He, Shaoxian Li, Haifeng Li, Chao Tao单位&#xff1a;中南大学地球科学与信息物理学院论文标题&#xff1a;BEDI: A Comprehensive Benchmark for Evaluating Embodied Agents on UAVs论文链接&#xff1a;https://arxiv.…...

基于uniapp+WebSocket实现聊天对话、消息监听、消息推送、聊天室等功能,多端兼容

基于 ​UniApp + WebSocket​实现多端兼容的实时通讯系统,涵盖WebSocket连接建立、消息收发机制、多端兼容性配置、消息实时监听等功能,适配​微信小程序、H5、Android、iOS等终端 目录 技术选型分析WebSocket协议优势UniApp跨平台特性WebSocket 基础实现连接管理消息收发连接…...

使用分级同态加密防御梯度泄漏

抽象 联邦学习 &#xff08;FL&#xff09; 支持跨分布式客户端进行协作模型训练&#xff0c;而无需共享原始数据&#xff0c;这使其成为在互联和自动驾驶汽车 &#xff08;CAV&#xff09; 等领域保护隐私的机器学习的一种很有前途的方法。然而&#xff0c;最近的研究表明&…...

Rust 异步编程

Rust 异步编程 引言 Rust 是一种系统编程语言,以其高性能、安全性以及零成本抽象而著称。在多核处理器成为主流的今天,异步编程成为了一种提高应用性能、优化资源利用的有效手段。本文将深入探讨 Rust 异步编程的核心概念、常用库以及最佳实践。 异步编程基础 什么是异步…...

学校时钟系统,标准考场时钟系统,AI亮相2025高考,赛思时钟系统为教育公平筑起“精准防线”

2025年#高考 将在近日拉开帷幕&#xff0c;#AI 监考一度冲上热搜。当AI深度融入高考&#xff0c;#时间同步 不再是辅助功能&#xff0c;而是决定AI监考系统成败的“生命线”。 AI亮相2025高考&#xff0c;40种异常行为0.5秒精准识别 2025年高考即将拉开帷幕&#xff0c;江西、…...

Redis的发布订阅模式与专业的 MQ(如 Kafka, RabbitMQ)相比,优缺点是什么?适用于哪些场景?

Redis 的发布订阅&#xff08;Pub/Sub&#xff09;模式与专业的 MQ&#xff08;Message Queue&#xff09;如 Kafka、RabbitMQ 进行比较&#xff0c;核心的权衡点在于&#xff1a;简单与速度 vs. 可靠与功能。 下面我们详细展开对比。 Redis Pub/Sub 的核心特点 它是一个发后…...

C++:多态机制详解

目录 一. 多态的概念 1.静态多态&#xff08;编译时多态&#xff09; 二.动态多态的定义及实现 1.多态的构成条件 2.虚函数 3.虚函数的重写/覆盖 4.虚函数重写的一些其他问题 1&#xff09;.协变 2&#xff09;.析构函数的重写 5.override 和 final关键字 1&#…...

Python 实现 Web 静态服务器(HTTP 协议)

目录 一、在本地启动 HTTP 服务器1. Windows 下安装 node.js1&#xff09;下载安装包2&#xff09;配置环境变量3&#xff09;安装镜像4&#xff09;node.js 的常用命令 2. 安装 http-server 服务3. 使用 http-server 开启服务1&#xff09;使用 http-server2&#xff09;详解 …...