当前位置: 首页 > 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的迁移…...

别再只调包了!手把手拆解OpenCV车位识别核心代码:像素统计、背景建模与形态学处理

从像素到决策&#xff1a;OpenCV车位识别核心技术实战解析 停车场监控画面中那些看似简单的"空"或"满"状态判定&#xff0c;背后隐藏着一系列精妙的图像处理魔法。今天&#xff0c;我们将抛开现成的API&#xff0c;直接解剖计算机视觉在车位检测中的核心算…...

告别预编译固件:手把手教你从零构建Pico PC RK3588S的Ubuntu 20.04根文件系统

深度定制RK3588S开发板&#xff1a;从零构建Ubuntu 20.04根文件系统的完整指南 当拿到一块全新的Pico PC RK3588S开发板时&#xff0c;许多开发者会发现厂商仅提供了预编译的固件包。这种"黑盒"模式虽然能快速启动设备&#xff0c;却严重限制了系统级定制的可能性。…...

漫画收藏自由:picacomic-downloader的离线阅读解决方案

漫画收藏自由&#xff1a;picacomic-downloader的离线阅读解决方案 【免费下载链接】picacomic-downloader 哔咔漫画 picacomic pica漫画 bika漫画 PicACG 多线程下载器&#xff0c;带图形界面 带收藏夹&#xff0c;已打包exe 下载速度飞快 项目地址: https://gitcode.com/gh…...

告别传统拍摄:THE LEATHER ARCHIVE低成本生成高质量皮衣展示图

告别传统拍摄&#xff1a;THE LEATHER ARCHIVE低成本生成高质量皮衣展示图 1. 时尚行业的数字革命 在时尚电商领域&#xff0c;商品展示图的质量直接影响消费者的购买决策。传统皮衣拍摄面临三大痛点&#xff1a; 高昂成本&#xff1a;专业模特、摄影师、场地租赁等费用动辄…...

从LeetCode到ACM:迷宫最短路径的C++ BFS模板,这么写就对了

从LeetCode到ACM&#xff1a;迷宫最短路径的C BFS模板实战精解 在算法竞赛和面试刷题中&#xff0c;迷宫类问题是最经典的场景之一。无论是LeetCode上的简单矩阵遍历&#xff0c;还是ACM竞赛中复杂的路径搜索&#xff0c;广度优先搜索&#xff08;BFS&#xff09;都是解决这类问…...

LH6828@ACP#6828#484 USB3.1 全通道 4:1/1:4 10Gbps 多路复用 / 解复用器 产品规格、应用分享及CH484规格对比

LH6828 是一款高性能全通道高速双向无源开关&#xff0c;专为 USB Type-C 生态系统设计&#xff0c;深度适配 USB3.1 Gen1&#xff08;5Gbps&#xff09;/Gen2&#xff08;10Gbps&#xff09;超高速传输协议&#xff0c;支持 4 组设备全通道信号的 4:1/1:4 双向切换&#xff0c…...

记录下在Windows中如何远程将当前Windows部署成PVE

背景&#xff1a; 做这件事实属无奈&#xff0c;公司另外一个分支的一个服务器(目前是Windows)需要跑多个平台的服务&#xff0c;目前Windows Server上部署虚拟机&#xff0c;直接装VMware workstation性能实在是糟糕&#xff0c;迫不得已考虑远程(无显示器、无KVM)将Windows …...

降本增效破局AI落地,中小企业Java团队的低成本入局路径

AI落地从不是大企业的专属&#xff0c;在大模型技术普惠的当下&#xff0c;Java生态企业尤其是中小企业&#xff0c;无需投入巨额成本、搭建专业AI团队&#xff0c;也能实现AI能力的快速接入与系统智能化改造。JBoltAI作为企业级Java AI应用开发框架&#xff0c;从技术框架、开…...

AI背景分离革新性全攻略:ComfyUI-BiRefNet创意工作流零基础上手指南

AI背景分离革新性全攻略&#xff1a;ComfyUI-BiRefNet创意工作流零基础上手指南 【免费下载链接】ComfyUI-BiRefNet-ZHO Better version for BiRefNet in ComfyUI | Both img & video 项目地址: https://gitcode.com/gh_mirrors/co/ComfyUI-BiRefNet-ZHO 在数字创意…...

从抓包实战出发:用Wireshark解密HTTP请求背后的TCP三次握手与挥手

从抓包实战出发&#xff1a;用Wireshark解密HTTP请求背后的TCP三次握手与挥手 当我们在浏览器中输入一个网址按下回车时&#xff0c;屏幕背后正上演着一场精密的协议芭蕾。作为开发者&#xff0c;你是否曾好奇&#xff1a;那些教科书上的TCP三次握手理论&#xff0c;在真实网络…...