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

【Java--数据结构】二叉树oj题(上)

前言

欢迎关注个人主页:逸狼


创造不易,可以点点赞吗~

如有错误,欢迎指出~



判断是否是相同的树

oj链接

要判断树是否一样,要满足3个条件

  • 结构 和 值 一样
  • 左子树的结构和值一样
  • 右子树的结构和值一样

所以就可以总结以下思路:

  1. 一个为空,一个不为空--》一定不相同
  2. 两个都为空--》                  相同
  3. 都不为空 ,但值不一样--》一定不相同
  4. 最后递归判断 左子树和右子树都要相同--》两棵树相同

其中该题的时间复杂度为O(min(m,n)),也就是取m和n中最小值(假设p的节点数为m个,q的节点数为n个)

public boolean isSameTree(TreeNode p, TreeNode q) {//一个为空,一个不为空if(p!=null&&q==null||p==null&&q!=null){return false;}//此时要么两个都为空,要么都不为空if(p==null&&q==null){return true;}//都不为空if(p.val!=q.val){return false;}//此时两个都不为空,val值也一样,说明根节点相同//判断左右树是否相同return isSameTree(p.left,q.left)&&isSameTree(p.right,q.right);

另一棵树的子树

oj链接

当两颗树相同时,也属于子树

所以步骤如下

  1. 判断是不是两颗相同的树
  2. 若不是,有可能是子树的子树
  3. 也有可能是子树的子树

其中该题的时间复杂度为m*n  (假设root有n个节点,subRoot有m个节点),原因是root的每一个节点都要和subRoot的节点比对

    public boolean isSubtree(TreeNode root, TreeNode subRoot) {//因为root要递归,递归到后面root可能为空if(root==null){return false;}//两颗树相同时,成立if(isSameTree(root,subRoot)){return true;}//判断root的左子树和subRootif(isSubtree(root.left,subRoot)){return true;}//判断root的右子树和subRootif(isSubtree(root.right,subRoot)){return true;}return false;}public boolean isSameTree(TreeNode p, TreeNode q) {//一个为空,一个不为空if(p!=null&&q==null||p==null&&q!=null){return false;}//此时要么两个都为空,要么都不为空if(p==null&&q==null){return true;}//都不为空if(p.val!=q.val){return false;}//此时两个都不为空,val值也一样,说明根节点相同//判断左右树是否相同return isSameTree(p.left,q.left)&&isSameTree(p.right,q.right);}

翻转二叉树

oj链接

让root的左节点和右节点交换,再递归遍历root.left和root.right使左子树和右子树都翻转。

代码优化:若只有一个根节点(左右子树都为空),直接返回;减少了递归和交换的次数

    public TreeNode invertTree(TreeNode root) {if(root==null){return null;}//代码优化部分******减少一些递归和交换的次数if(root.left==null&&root.right==null){return root;}//          ******TreeNode ret=root.left;root.left=root.right;root.right=ret;invertTree(root.left);invertTree(root.right);return root;}

判断一颗二叉树是否是平衡二叉树

平衡二叉树 是指该树所有节点的左右子树的深度相差不超过 1

oj链接

 判断步骤:

当前root的 左子树 和 右子树的高度差<=1

同时满足root的左 右子树平衡

 其中该题的时间复杂度为O(n^2)

    public boolean isBalanced(TreeNode root) {if(root==null) return true;int leftH=maxDepth(root.left);int rightH=maxDepth(root.right);return Math.abs(leftH-rightH)<=1&&isBalanced(root.left)&&isBalanced(root.right);}public int maxDepth(TreeNode root){if(root==null){return 0;}int leftH=maxDepth(root.left);int rightH=maxDepth(root.right);return leftH>rightH?leftH+1:rightH+1;}

 代码优化,使得时间复杂度变为O(n)

    public boolean isBalanced(TreeNode root) {if(root==null) return true;return maxDepth(root)>=1;}public int maxDepth(TreeNode root){if(root==null){return 0;}int leftH=maxDepth(root.left);if(leftH<0){return -1;}int rightH=maxDepth(root.right);if(rightH<0){return -1;}if(Math.abs(leftH-rightH)<=1){return leftH>rightH?leftH+1:rightH+1;}else{return -1;}}

第三种写法

    public boolean isBalanced(TreeNode root) {if(root==null) return true;return maxDepth(root)>=1;}public int maxDepth(TreeNode root){if(root==null){return 0;}int leftH=maxDepth(root.left);// if(leftH<0){//     return -1; // }int rightH=maxDepth(root.right);// if(rightH<0){//     return -1;// }if(leftH>=0&&rightH>=0&&Math.abs(leftH-rightH)<=1){return Math.max(leftH,rightH)+ 1;}else{return -1;}}

相关文章:

【Java--数据结构】二叉树oj题(上)

前言 欢迎关注个人主页&#xff1a;逸狼 创造不易&#xff0c;可以点点赞吗~ 如有错误&#xff0c;欢迎指出~ 判断是否是相同的树 oj链接 要判断树是否一样&#xff0c;要满足3个条件 根的 结构 和 值 一样左子树的结构和值一样右子树的结构和值一样 所以就可以总结以下思路…...

微服务之间Feign调用

需使用的服务 FeignClient(name "rdss-back-service", fallback SysUserServiceFallback.class, configuration FeignConfiguration.class) public interface SysUserService {/*** 订单下单用户模糊查询*/GetMapping(value "/user/getOrderUserName")…...

【Qt】按钮的属性相关API

目录 一. QPushButton 二. QRadioButton 按钮组 三. QCheckBox Qt中按钮的继承体系如下图 QAbstractButton是一个抽象类&#xff0c;集成了按钮的核心属性和API 按钮说明QPushButton&#xff08;普通按钮&#xff09;最常见的按钮&#xff0c;用于触发操作或者事件。可以设…...

blender和3dmax和maya和c4d比较

Blender、3ds Max、Maya和Cinema 4D (C4D)都是强大的3D建模和动画软件&#xff0c;但它们各有特点和适用领域。以下是它们的比较&#xff1a; Blender: 开源免费全面的功能&#xff0c;包括建模、动画、渲染、视频编辑等学习曲线较陡峭&#xff0c;但社区支持强大适合独立艺术家…...

visio保存一部分图/emf图片打开很模糊/emf插入到word或ppt中很模糊

本文主要解决三个问题 visio保存一部分图 需求描述&#xff1a;在一个visio文件中画了很多个图&#xff0c;但我只想把其中一部分保存成某种图片格式&#xff0c;比如jpg emf png之类的&#xff0c;以便做后续的处理。 方法&#xff1a;超级容易。 选中希望保存的这部分图&…...

沙尘传输模拟教程(基于wrf-chem)

沙尘传输模拟教程(基于wrf-chem) 文章目录 沙尘传输模拟教程(基于wrf-chem)简介实验目的wrf-chem简介 软件准备wps、wrf-chem安装conda安装ncl安装ncap安装 数据准备气象数据准备下垫面数据准备 WPS数据预处理namelist.wps的设置geogrid.exe下垫面处理ungrib.exe气象数据预处理…...

使用 Python 进行测试(8)纯净测试

原文&#xff1a;Testing with Python (part 8): purity test 总结 如果你要使用综合测试&#xff08;integrated tests&#xff09;&#xff1a; def test_add_new_item_to_cart(product, cart):new_product Product.objects.create(nameNew Product, price15.00)new_cart…...

python的tkinter、socket库开发tcp的客户端和服务端

一、tcp通讯流程和开发步骤 1、tcp客户端和服务端通讯流程图 套接字是通讯的利器&#xff0c;连接时要经过三次握手建立连接&#xff0c;断开连接要经过四次挥手断开连接。 2、客户端开发流程 1&#xff09;创建客户端套接字 2&#xff09;和服务端器端套接字建立连接 3&#x…...

Python面试题:Python中的异步编程:详细讲解asyncio库的使用

Python 的异步编程是实现高效并发处理的一种方法&#xff0c;它使得程序能够在等待 I/O 操作时继续执行其他任务。在 Python 中&#xff0c;asyncio 库是实现异步编程的主要工具。asyncio 提供了一种机制来编写可以在单线程内并发执行的代码&#xff0c;适用于 I/O 密集型任务。…...

【信号频率估计】MVDR算法及MATLAB仿真

目录 一、MVDR算法1.1 简介1.2 原理1.3 特点1.3.1 优点1.3.2 缺点 二、算法应用实例2.1 信号的频率估计2.2 MATLAB仿真代码 三、参考文献 一、MVDR算法 1.1 简介 最小方差无失真响应&#xff08;Mininum Variance Distortionless Response&#xff0c;MVDR&#xff09;算法最…...

HarmonyOS NEXT零基础入门到实战-第二部分

HarmonyOS NEXT零基础入门到实战-第二部分 Swiper 轮播组件 Swiper是一个 容器 组件&#xff0c;当设置了多个子组件后&#xff0c;可以对这些 子组件 进行轮播显示。&#xff08;文字、图片...&#xff09; 1、Swiper基本语法 2、Swiper常见属性 3、Swiper样式自定义 4、案例&…...

《小程序02:云开发之增删改查》

一、前置操作 // 一定要用这个符号包含里面的${}才会生效 wx.showToast({title: 获取数据成功&#xff1a;${colorLista}, })1.1&#xff1a;初始化介绍 **1、获取数据库引用&#xff1a;**在开始使用数据库 API 进行增删改查操作之前&#xff0c;需要先获取数据库的引用 cons…...

SQL执行流程、SQL执行计划、SQL优化

select查询语句 select查询语句中join连接是如何工作的&#xff1f; 1、INNER JOIN 返回两个表中的匹配行。 2、LEFT JOIN 返回左表中的所有记录以及右表中的匹配记录。 3、RIGHT JOIN 返回右表中的所有记录以及左表中的匹配记录。 4、FULL OUTER JOIN 返回左侧或右侧表中有匹…...

【前端】JavaScript入门及实战41-45

文章目录 41 嵌套的for循环42 for循环嵌套练习(1)43 for循环嵌套练习(2)44 break和continue45 质数练习补充 41 嵌套的for循环 <!DOCTYPE html> <html> <head> <title></title> <meta charset "utf-8"> <script type"…...

更加深入Mysql-04-MySQL 多表查询与事务的操作

文章目录 多表查询内连接隐式内连接显示内连接 外连接左外连接右外连接 子查询 事务事务隔离级别 多表查询 有时我们不仅需要一个表的数据&#xff0c;数据可能关联到俩个表或者三个表&#xff0c;这时我们就要进行夺标查询了。 数据准备&#xff1a; 创建一个部门表并且插入…...

基于最新版的flutter pointycastle: ^3.9.1的AES加密

基于最新版的flutter pointycastle: ^3.9.1的AES加密 自己添加pointycastle: ^3.9.1库config.dartaes_encrypt.dart 自己添加pointycastle: ^3.9.1库 config.dart import dart:convert; import dart:typed_data;class Config {static String password 成都推理计算科技; // …...

K8S内存资源配置

在 Kubernetes (k8s) 中&#xff0c;资源请求和限制用于管理容器的 CPU 和内存资源。配置 CPU 和内存资源时&#xff0c;使用特定的单位来表示资源的数量。 CPU 资源配置 CPU 单位&#xff1a;Kubernetes 中的 CPU 资源以 “核” (cores) 为单位。1 CPU 核心等于 1 vCPU/Core…...

【多任务YOLO】 A-YOLOM: You Only Look at Once for Real-Time and Generic Multi-Task

You Only Look at Once for Real-Time and Generic Multi-Task 论文链接&#xff1a;http://arxiv.org/abs/2310.01641 代码链接&#xff1a;https://github.com/JiayuanWang-JW/YOLOv8-multi-task 一、摘要 高精度、轻量级和实时响应性是实现自动驾驶的三个基本要求。本研究…...

数学建模--灰色关联分析法

目录 简介 基本原理 应用场景 优缺点 优点&#xff1a; 缺点&#xff1a; 延伸 灰色关联分析法在水质评价中的具体应用案例是什么&#xff1f; 如何克服灰色关联分析法在主观性强时的数据处理和改进方法&#xff1f; 灰色关联分析法与其他系统分析方法&#xff08;如A…...

NetSuite Saved Search迁移工具

我们需要在系统间迁移Saved Search&#xff0c;但是采用Copy To Account或者Bundle时&#xff0c;会有一些Translation不能迁移&#xff0c;或者很多莫名其妙的Dependency&#xff0c;导致迁移失败。因此&#xff0c;我们想另辟蹊径&#xff0c;借助代码完成Saved Search的迁移…...

Neeshck-Z-lmage_LYX_v2实战教程:异常友好提示机制与错误定位指南

Neeshck-Z-lmage_LYX_v2实战教程&#xff1a;异常友好提示机制与错误定位指南 1. 引言&#xff1a;当绘画工具变得“会说话” 想象一下&#xff0c;你兴致勃勃地打开一个AI绘画工具&#xff0c;输入了一段精心构思的描述&#xff0c;点击生成&#xff0c;然后……页面卡住了。…...

Windows Insider离线管理完全指南:无账户切换方法与命令行操作技巧

Windows Insider离线管理完全指南&#xff1a;无账户切换方法与命令行操作技巧 【免费下载链接】offlineinsiderenroll 项目地址: https://gitcode.com/gh_mirrors/of/offlineinsiderenroll 在Windows系统管理中&#xff0c;用户常常面临需要在不同更新通道间切换的需求…...

专业流媒体视频下载工具技术解析与使用指南

专业流媒体视频下载工具技术解析与使用指南 价值主张&#xff1a;高效解决流媒体内容本地化需求 在数字内容消费日益普及的今天&#xff0c;用户对在线视频资源的本地保存需求持续增长。m3u8-downloader作为一款专业的流媒体下载工具&#xff0c;专注于解决m3u8格式视频的高效…...

从CTF逆向实战出发:手把手教你用Python脚本破解RC4和Base58加密(附完整代码)

从CTF逆向实战出发&#xff1a;手把手教你用Python脚本破解RC4和Base58加密&#xff08;附完整代码&#xff09; 在CTF竞赛中&#xff0c;逆向工程题目往往涉及各种加密算法的识别与破解。本文将聚焦两种常见加密方式——RC4和Base58&#xff0c;通过Python脚本实现从算法识别到…...

公开信息整理|2026年3月26日:科学进展、词元活动、食品安全、护理保险与部分国际动态速览

&#x1f525;个人主页&#xff1a;杨利杰YJlio❄️个人专栏&#xff1a;《Sysinternals实战教程》《Windows PowerShell 实战》《WINDOWS教程》《IOS教程》《微信助手》《锤子助手》 《Python》 《Kali Linux》 《那些年未解决的Windows疑难杂症》&#x1f31f; 让复杂的事情更…...

从航拍影像到三维地形:OpenDroneMap实战指南与常见问题解答

从航拍影像到三维地形&#xff1a;OpenDroneMap实战指南与常见问题解答 【免费下载链接】ODM A command line toolkit to generate maps, point clouds, 3D models and DEMs from drone, balloon or kite images. &#x1f4f7; 项目地址: https://gitcode.com/gh_mirrors/od…...

CentOS 7.9 上TDengine 3.0.4.2 二进制安装避坑指南:从下载到压测一条龙

CentOS 7.9 上TDengine 3.0.4.2 二进制安装实战&#xff1a;从零部署到百万级压测全解析 时序数据库正在成为物联网、工业互联网和金融监控等场景的核心基础设施。作为国产时序数据库的佼佼者&#xff0c;TDengine以其卓越的写入性能和压缩比&#xff0c;正在全球范围内获得越…...

AI辅助开发实战:基于CosyVoice和LeeZhao的智能代码生成优化

在AI辅助开发的浪潮中&#xff0c;我们这些开发者既兴奋又头疼。兴奋的是&#xff0c;动动嘴皮子或者写几句描述&#xff0c;AI就能帮我们生成代码框架&#xff0c;大大提升了效率。头疼的是&#xff0c;生成的代码常常“驴唇不对马嘴”&#xff0c;要么上下文理解跑偏&#xf…...

OpenClaw+nanobot学术助手:文献自动归类与摘要生成

OpenClawnanobot学术助手&#xff1a;文献自动归类与摘要生成 1. 为什么需要自动化文献管理工具 作为一名经常需要阅读大量论文的研究者&#xff0c;我长期被文献管理问题困扰。电脑里堆积如山的PDF文件&#xff0c;每次需要查找特定内容时都要花费大量时间翻找。更痛苦的是&…...

RK3568 Android12长按电源键无反应?三步搞定关机菜单恢复

RK3568 Android12电源键功能失效排查与深度修复指南 在RK3568平台上进行Android12系统定制时&#xff0c;电源键功能异常是开发者常遇到的典型问题。不同于简单的功能缺失&#xff0c;这背后涉及系统级行为配置、手势交互逻辑和硬件抽象层的多层级适配。本文将带您从现象溯源到…...