2024.(3.30和4.1)力扣刷题记录-二叉树学习记录2

news/2024/4/15 15:03:16

一、学习视频

如何灵活运用递归?【基础算法精讲 10】_哔哩哔哩_bilibili

二、跟练代码

1. 100. 相同的树

递归

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:# 递归if p is None and q is None:return Trueelif p is None or q is None:return Falseleft = self.isSameTree(p.left,q.left)right = self.isSameTree(p.right,q.right)return left and right and p.val == q.val

学习一下灵神的写法,来自视频。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:# 递归# if p is None and q is None:#     return True# elif p is None or q is None:#     return Falseif p is None or q is None:return p is qleft = self.isSameTree(p.left,q.left)right = self.isSameTree(p.right,q.right)return left and right and p.val == q.val

2.101. 对称二叉树

递归

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:def isSymmetric(self, root: Optional[TreeNode]) -> bool:# 递归# 含有根节点# 判断根节点的左右两子树def f(left: Optional[TreeNode], right: Optional[TreeNode]) -> bool:if left is None or right is None:return left is rightreturn f(left.left,right.right) and f(left.right,right.left) and left.val == right.val# #根节点为空时是满足的,此处含根节点可以省去# if root is None:    #     return Truereturn f(root.left,root.right)

3.110. 平衡二叉树

递归。不会,来自视频代码。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:def isBalanced(self, root: Optional[TreeNode]) -> bool:# 递归# 计算高度,非负数# 用-1表示不是平衡二叉树def f(node) -> int:if node is None:return 0# left_h = f(node.left)# right_h = f(node.right)# if left_h == -1 or right_h == -1 or abs(left_h - right_h) > 1:#     return -1# return max(left_h, right_h) + 1# 少递归一些left_h = f(node.left)if left_h == -1:return -1right_h = f(node.right)if right_h == -1 or abs(left_h - right_h) > 1:return -1return max(left_h, right_h) + 1return f(root) != -1

4.199. 二叉树的右视图

递归

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:def rightSideView(self, root: Optional[TreeNode]) -> List[int]:# 递归# 先右后左遍历,当高度大于minHeight时,才会露出来ans = []minHeight = 0def f(node,height):nonlocal minHeightif node is None:return if height > minHeight:ans.append(node.val)minHeight += 1right = f(node.right,height + 1)left = f(node.left,height + 1)return f(root,1)return ans

三、课后作业

1.226. 翻转二叉树

递归

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:# 递归if root is None:return Noneleft = self.invertTree(root.left)   #左子树right = self.invertTree(root.right) #右子树root.left = right   #左右互换root.right = leftreturn root

2.1026. 节点与其祖先之间的最大差值

不会,全都来自灵神题解(. - 力扣(LeetCode)),学习学习。

(1)递

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:def maxAncestorDiff(self, root: Optional[TreeNode]) -> int:# 递v = -1def f(node,mx,mn):nonlocal vif node is None:return  #不一定要有返回值mx = max(mx,node.val)mn = min(mn,node.val)v = max(v, node.val - mn, mx - node.val)    #更新f(node.left,mx,mn)f(node.right,mx,mn)f(root, root.val, root.val)     #根节点存在return v

(2)递的优化

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:def maxAncestorDiff(self, root: Optional[TreeNode]) -> int:# 递的优化v = -1def f(node,mx,mn):if node is None:nonlocal vv = max(v, mx - mn)    #到终点更新returnmx = max(mx,node.val)mn = min(mn,node.val)f(node.left,mx,mn)f(node.right,mx,mn)f(root, root.val, root.val)     #根节点存在return v

(3)归

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:def maxAncestorDiff(self, root: Optional[TreeNode]) -> int:# 归v = -1def f(node):if node is None:return inf, -inf    # min maxmn = mx = node.vallmin, lmax = f(node.left)rmin, rmax = f(node.right)mn = min(mn, lmin, rmin)mx = max(mx, lmax, rmax)nonlocal v# 每一次都更新vv = max(v, node.val - mn, mx - node.val)return mn, mxf(root)return v

递可以不用每次都更新v值,因为从上到下能确保最大小值就是该条路径的,而没有受其他路径影响;而归每次都需更新v值,一个节点有左右两边两条路径到达。

3.1080. 根到叶路径上的不足节点

(1)递归。参考官方题解(. - 力扣(LeetCode))。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:def sufficientSubset(self, root: Optional[TreeNode], limit: int) -> Optional[TreeNode]:# 递归# 递总值 归是否删除(False删)def f(node, s):if node is None:return Falseif node.left is None and node.right is None:return s + node.val >= limitleft = f(node.left, s + node.val)right = f(node.right, s + node.val)if not left:node.left = Noneif not right:node.right = Nonereturn left or rightrootBool = f(root, 0)return root if rootBool else None

注意删除节点不能本节点直接删除,要在上一节点删除(删除联系)。

(2)递归(调用自身写法)。参考灵神题解(. - 力扣(LeetCode))。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:def sufficientSubset(self, root: Optional[TreeNode], limit: int) -> Optional[TreeNode]:# 递归(调用自身写法)# 通过更改limit实现求和的作用if root is None:return Noneif root.left is root.right: #为叶子节点return root if root.val >= limit else Noneroot.left = self.sufficientSubset(root.left, limit - root.val)root.right = self.sufficientSubset(root.right, limit - root.val)return root if root.left or root.right else None

可以通过 root.left is root.right 来判断是不是叶子节点。

4.1372. 二叉树中的最长交错路径

(1)递归+非局部变量

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:def longestZigZag(self, root: Optional[TreeNode]) -> int:# 递归+非局部变量# 递标签,归和值ans = 0def f(node: Optional[TreeNode], flag: str) -> int:nonlocal ansif node is None:return 0left = f(node.left, 'left')right = f(node.right, 'right')if flag == 'left':  #该节点是父节点的左节点,下一步该右节点ans = max(ans, left)    #更新左节点和值return right+1      #继续归右节点和值else:ans = max(ans, right)return left+1# 更新最终返回值ans = max(f(root.left,"left"),f(root.right,"right"),ans)return ans

(2)递归+非局部变量2。来自题解(. - 力扣(LeetCode)),很妙很妙。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:def longestZigZag(self, root: Optional[TreeNode]) -> int:# 递归+非局部变量2ans = 0def f(node, l, r):  #递左右最大值nonlocal ansans = max(ans, l, r)if node.left:f(node.left, r+1, 0)if node.right:f(node.right, 0, l+1)f(root, 0, 0)return ans

感谢你看到这里!一起加油吧!


http://www.ppmy.cn/news/1405590.html

相关文章

Redis高可用技术

一.Redis高可用介绍: 高可用是指:服务器正常访问的时间 衡量的标准是:在多长时间内可以提供正常服务99.9%、99.99%、99.999%等等 但是在Redis语境中, 高可用的含义似乎要宽泛一些,除了保证提供正常服务(如主从分离、…

Python快速入门系列-8(Python数据分析与可视化)

第八章:Python数据分析与可视化 8.1 数据处理与清洗8.1.1 数据加载与查看8.1.2 数据清洗与处理8.1.3 数据转换与整理8.2 数据可视化工具介绍8.2.1 Matplotlib8.2.2 Seaborn8.2.3 Plotly8.3 数据挖掘与机器学习简介8.3.1 Scikit-learn8.3.2 TensorFlow总结在本章中,我们将探讨…

【智能算法】蜜獾算法(HBA)原理及实现

目录 1.背景2.算法原理2.1算法思想2.2算法过程 3.结果展示4.参考文献 1.背景 2021年,FA Hashim等人受到自然界中蜜獾狩猎行为启发,提出了蜜獾算法((Honey Badger Algorithm,HBA)。 2.算法原理 2.1算法思想 蜜獾以其…

关于网络丢包的一种可能性分析

最近我在工作中经常遇到有些客户的网络传输性能不理想。 通过wireshark抓包后我发现经常会有稍大的包timeout需要重传,这个现象导致了网络传输效率的大幅下降,因此我对网络丢包方面进行了进一步的研究。 根据我的经验总结,网络丢包有两种情况…

JVM 记录

记录 工具 https://gceasy.io 资料 尚硅谷宋红康JVM全套教程(详解java虚拟机) https://www.bilibili.com/video/BV1PJ411n7xZ?p361 全套课程分为《内存与垃圾回收篇》《字节码与类的加载篇》《性能监控与调优篇》三个篇章。 上篇《内存与垃圾回收篇…

【C+ +】第一个C+ + 项目的创建及namespace命名空间解释C++中的输入输出

目录 1.创建第一个c项目 1.1项目创建 1.2 .cpp源文件建立 1.3 第一个c程序hello world对比c语言hello world 2.命名空间 2.1 C关键字 2.2 命名空间---解决c语言中的命名冲突 2.2.1 namespace命名空间用法 2.2.2 :: 预作用限定符 2.2.3 命名空间的嵌套…

搭建跨境电商电商独立站如何接入1688平台API接口|通过1688API接口采集商品通过链接搜索商品下单

接口设计|接口接入 对于mall项目中商品模块的接口设计,大家可以参考项目的Swagger接口文档,以Pms开头的接口就是商品模块对应的接口。 参数说明 通用参数说明 参数不要乱传,否则不管成功失败都会扣费url说明……d.cn/平台/API类型/ 平台&…

Lumos学习王佩丰Excel第一讲:认识Excel

最近发现自己在操作excel的一些特殊功能时会有些不顺手,所以索性找了一个比较全的教程(王佩丰excel24讲)拿来学习,刚好形成文档笔记,分享给有需要但没有时间看视频的朋友们。整体笔记以王老师授课的知识点去记录&#…

基本环境搭建指南

前端相关 Nodejs 官网下载:https://nodejs.cn/ 网盘下载:https://yun.mllt.cc/s/Rvtm 数据库相关 MySQL https://dev.mysql.com/downloads/mysql/5.7.html navcat https://navicat.com.cn/products redis 官网下载:https://redis.io/docs/ins…

自适应动态规划硕士博士论文学习

基于自适应动态规划的非线性系统最优控制-南邮硕毕 主要内容: 外部扰动下,基于事件触发自适应动态规划。设计触发阈值,由评价网络近似性能指标函数,两个动作网络分别逼近控制输入和外部扰动。外部扰动和状态约束下,基…

Neo4j基础知识

图数据库简介 图数据库是基于数学里图论的思想和算法而实现的高效处理复杂关系网络的新型数据库系统。它善于高效处理大量的、复杂的、互连的、多变的数据。其计算效率远远高于传统的关系型数据库。 在图形数据库当中,每个节点代表一个对象,节点之间的…

Windows下Docker安装Kafka3+集群

编写 docker-compose.yaml 主要参照:https://www.cnblogs.com/wangguishe/p/17563274.html version: "3"services:kafka1:image: bitnami/kafka:3.4.1container_name: kafka1environment:- KAFKA_HEAP_OPTS-Xmx1024m -Xms1024m- KAFKA_ENABLE_KRAFTyes- K…

MySQL的基本操作(超详细)

👨‍💻作者简介:👨🏻‍🎓告别,今天 📔高质量专栏 :☕java趣味之旅 📔(零基础)专栏:MSQL数据库 欢迎🙏点赞&…

路径优化算法 | 基于A_Star算法实现复杂地形下无人机威胁概率地图最短路径避障三维航迹规划

概述 A* (A-Star) 算法是一种广泛使用的路径搜索和图形遍历算法,用于在给定起点和终点的情况下找到最短路径。对于无人机在复杂地形下的三维航迹规划,A* 算法可以与其他技术结合,例如威胁概率地图(Threat Probability Map),以实现避障和最短路径规划。 以下是一个基于 …

AI音乐GPT时刻来临:Suno 快速入门手册!

✨✨ 欢迎大家来访Srlua的博文(づ ̄3 ̄)づ╭❤~✨✨ 🌟🌟 欢迎各位亲爱的读者,感谢你们抽出宝贵的时间来阅读我的文章。 我是Srlua小谢,在这里我会分享我的知识和经验。&am…

基于springboot实现校园周边美食探索及分享平台系统项目【项目源码+论文说明】

基于springboot实现园周边美食探索及分享平台系统演示 摘要 美食一直是与人们日常生活息息相关的产业。传统的电话订餐或者到店消费已经不能适应市场发展的需求。随着网络的迅速崛起,互联网日益成为提供信息的最佳俱渠道和逐步走向传统的流通领域,传统的…

成员变量没有多态性

若子类重写了父类方法,就意味着子类里定义的方法彻底覆盖了父类里的同名方法,系统将不可能把父类里的方法转移到子类中。 对于实例变量则不存在这样的现象,即使子类里定义了与父类完全相同的实例变量,这个实例变量依然不可能覆盖…

基于8086贪吃蛇游戏系统方恨设计

**单片机设计介绍,基于8086贪吃蛇游戏系统方恨设计 文章目录 一 概要二、功能设计三、 软件设计原理图 五、 程序六、 文章目录 一 概要 基于8086的贪吃蛇游戏系统设计是一个结合了微处理器控制、游戏逻辑以及图形显示技术的综合性项目。该系统旨在通过8086微处理器…

实现顺序表的增删查改

现在让我们探索数据结构这个美妙的世界吧! 概念介绍 线性表是具有相同特性的数据元素的有限序列。线性表是一种在实际运用中广泛运用的线性结构,如线性表,栈,队列,字符串等。 顺序表的本质是数组,实现了…

Docker 笔记

1.Ubuntu安装Docker 安装Docker看这篇文章 http://t.csdnimg.cn/IsSsJ 2.在docker中运行python代码 2.1搭建python环境 docker部署python环境看这篇文章 http://t.csdnimg.cn/TYz0G 2.2在python shell中运行python代码 2.2.1查看镜像 2.2.1启动python,厦门这个…
最新文章