leetcode尊享面试100题(549二叉树最长连续序列||,python)

题目不长,就是分析时间太久了。

思路使用dfs深度遍历,先想好这个函数返回什么,题目给出路径可以是子-父-子的路径,那么1-2-3可以,3-2-1也可以,那么考虑dfs返回两个值,对于当前节点node来说,返回一个顺序的长度的最大值p,一个逆序长度的最大值b,初始值都为1。例如,当前节点值为3,下面有两个子节点1-2,那么p为3,b仍为1。

这是返回的值,那么对于当前节点,以node为终点的最大长度=max(p,b),还有一种经过node节点的路径需要考虑,例如,左节点为1,右节点为3,当前节点为2。

这题需要把所有的情况罗列一遍,就是多几个if语句!!!

class Solution:
    def __init__(self):
        self.m = 1

    def longestConsecutive(self, root: Optional[TreeNode]) -> int:
        self.dfs(root)
        return self.m
    
    def dfs(self, node):
        if not node: return 0, 0
        p, b, m = 1, 1, 1
        p1, b1 = self.dfs(node.left)
        p2, b2 = self.dfs(node.right)
        if node.left and abs(node.left.val - node.val) == 1:
            if node.left.val - node.val == -1:
                p = max(p, p1 + 1)
            else:
                b = max(b, b1 + 1)
        if node.right and abs(node.right.val - node.val) == 1:
            if node.right.val - node.val == -1:
                p = max(p, p2 + 1)
            else:
                b = max(b, b2 + 1)
        if node.left and node.right and node.left.val - node.val ==  node.val - node.right.val:
            if node.left.val - node.val == -1:
                m = b2 + p1 + 1
            elif node.left.val - node.val == 1:
                m = b1 + p2 + 1
        self.m = max(self.m, p, b, m)
        return p, b

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/608203.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

BI赋能金融新质生产力,16家金融机构智能BI创新实践分享

2024年政府工作报告强调,要“大力发展科技金融、绿色金融、普惠金融、养老金融、数字金融”,同时“大力推进现代化产业体系建设,加快发展新质生产力”。对于金融行业而言,培育新质生产力是高质量发展的关键着力点。金融机构可以通…

vue项目启动后页面显示‘Cannot GET /’

1、npm run dev命令启动项目的时候没有报错,页面打开却提示 Cannot GET / 2.这个时候只需要找到config文件夹下面的index.js文件。把assetsPublicPath字符串的:‘./’修改成 ‘/’就行了。修改完之后记得关闭项目,然后重新启动。不然不会生效…

度小满——征信报告图建模

目录 背景介绍 发展趋势 技术演进 图在金融风控领域中的演进 度小满图机器学习技术体系 案例 征信报告介绍 征信报告图建模

postman接口测试中文汉化教程

想必同学们对于接口测试工具postman的使用并不陌生,以及最近大为流行的国产工具apifox。对于使用过的同学来说,两者区别以及优缺点很容易别展示出来,postman相比apifox来说更加轻量,但是apifox更加符合国人的使用习惯....中国人给…

Nest 快速上手 —— (三)中间件 / 异常过滤器

一、 中间件(Middleware) 1.特点 中间件是一个在路由处理程序之前被调用的函数。中间件函数可以访问请求和响应对象,以及应用程序请求-响应周期中的next()中间件函数。下一个中间件函数通常由一个名为next的变量表示。 中间件函数可以执行以…

车载测试系列:车载蓝牙测试(三)

HFP测试内容与测试方法 2.3 接听来电:测试手机来电时,能否从车载蓝牙设备和手机侧正常接听】拒接、通话是否正常。 1、预置条件:待测手机与车载车载设备处于连接状态 2、测试步骤: 1)用辅助测试机拨打待测手机&…

BetterMouse for Mac激活版:鼠标增强软件

BetterMouse for Mac是一款鼠标增强软件,旨在取代笨重的、侵入性的和耗费资源的鼠标驱动程序,如罗技选项。它功能丰富,重量轻,效率优化,而且完全隐私安全,试图满足你在MacOS上使用第三方鼠标的所有需求。 B…

新火种AI|AI让大家都变“土”了!

作者:一号 编辑:美美 AI不仅要把人变“土”,还要把人变多样。 这个世界,终究是变“土”了。 今年五一假期,一个名为“Remini”的AI修图APP火遍了全网。注意,是Remini,而不是Redmi&#xff0…

MySQL-集群1

一、为什么要用mysql集群?: mysql单体架构在企业中很少用,原因:①会形成单点故障,没有高可用的效果;②mysql本身是一个I/O能力比较差,并发能力比较差的应用服务,在较高规模的网络I/…

部署JVS服务出现上传文件不可用,问题原因排查。

事情的起因是这样的,部门经理让我部署一下JVS资源共享框架,项目的地址是在这里 项目资源地址 各位小伙伴们做好了,我要开始发车了,全新的“裂开之旅” 简单展示一下如何部署JVS文档 直达链接 撕裂要开始了 本来服务启动的好好…

【计算机毕业设计】基于SSM++jsp的蜀都天香酒楼网站【源码+lw+部署文档+讲解】

目录 摘要 Abstract 目 录 1绪论 1.1研究背景与意义 1.2国内外研究现状 1.3研究内容 1.4论文结构 2相关技术介绍 2.1 B/S模式 2.2 MyEclipse开发环境 2.3 MySQL数据库 2.4 Java语言 2.5 JSP技术 2.6 Tomcat服务器 3系统分析 3.1需求分析 3.2可行性分析 3.2.1经济可行性 3.2.2技…

Python运维之多进程!!

本节的快速导航目录如下喔!!! 一、创建进程的类Process 二、进程并发控制之Semaphore 三、进程同步之Lock 四、进程同步之Event 五、进程优先队列Queue 六、多进程之进程池Pool 七、多进程之数据交换Pipe 一、创建进程的类Process mu…

5.9gunplot绘图堆叠柱状图

gunplot绘图堆叠柱状图 plot"要用的数据(后缀名是.dat)" using 2 t(或者title) 跟着是要命名的属性名称 这个名称可以用.dat里的每列列名,也可以直接在后面跟着定义 plot "data.dat" using 2 t columnheader(2), using 3 t column…

PLC数据采集网关的功能和特点-天拓四方

一、引言 随着工业自动化程度的不断提高,数据在生产线上的作用愈发重要。PLC作为工业自动化的核心设备,其数据采集和处理能力直接影响到整个生产线的效率和稳定性。而PLC数据采集网关,作为连接PLC与外部系统的桥梁,正日益受到人们…

vue3—win7搭建vue3环境

背景 vue3环境要求node.js18.3及以上版本,所以我们需要安装更高版本node.js,然而win7无法支持高版本node.js。下面我介绍一种安装方法。 步骤 1、下载 node-v13.14.0-x64.msi 安装,默认安装即可。安装完成后,进入cmd&#xff0c…

Hibernate认识

一、定义 Hibernate 是一种开源的 Java 对象关系映射 (ORM) 框架,用于将面向对象的领域模型持久化到关系数据库中。它为开发人员提供了一种简便的方法来操作数据库,而无需编写繁琐的 SQL 代码。 ORM(对象关系映射):Ob…

Linux 第二十章

🐶博主主页:ᰔᩚ. 一怀明月ꦿ ❤️‍🔥专栏系列:线性代数,C初学者入门训练,题解C,C的使用文章,「初学」C,linux 🔥座右铭:“不要等到什么都没有了…

提速25倍!MoonBit 新增后端支持,一周内成为热议焦点

MoonBit 新增 JS 后端支持 近期,MoonBit 迎来了重要更新:新增对 JavaScript 后端的支持,为用户带来了前所未有的性能提升。 MoonBit 诞生于2022年,是专为云计算及边缘计算设计的 AI 云原生编程语言及开发者平台。作为一门诞生于 …

Orange3数据可视化(小提琴图)

小提琴图 小提琴图和箱线图类似,用来显示数据分布和概率密度。结合了箱线图和密度图的特征,用来显示数据的分布形状。 输入 数据: 输入数据集 输出 选中的数据: 从图中选中的实例 数据: 增加了一列,显示数据点是否被选中 …

STM32--4G DTU 及 阿里云

模块概述 ATK-IDM750C/IDM751C 是正点原子(ALIENTEK)团队开发的一款高性能 4G Cat1 DTU 产品, 支持移动 4G、联通 4G 和电信 4G 手机卡。它以高速率、低延迟和无线数传作为核心功能, 可快速解决应用场景下的无线数传方案。 它支持 TCP/UDP/HTTP/MQTT/DN…