首页 > 其他分享 >Leetcode 3203. Find Minimum Diameter After Merging Two Trees

Leetcode 3203. Find Minimum Diameter After Merging Two Trees

时间:2024-06-30 19:58:16浏览次数:25  
标签:Diameter 3203 diameter int graph After depth leafs deg

1. 解题思路

这一题的话算是一个拓扑树的题目?总之就是从树的叶子节点不断向上遍历,不断地删除已访问的叶子节点,并加入更新之后的新的叶子节点,这样我们就能得到树的最大深度,然后在遍历过程中我们考察其任意节点上的当前深度和已有深度的和的最大值,即为经过该节点的最大路径长度,遍历整张图,我们即刻获得整个树的深度和diameter。然后,我们要连接两个图的话,能够获得的最大路径长度就是两个图的深度之和加一。

由此,我们即可完成这道题目了。

2. 代码实现

给出python代码实现如下:

class Solution:
    def minimumDiameterAfterMerge(self, edges1: List[List[int]], edges2: List[List[int]]) -> int:
        
        def dfs(edges):
            if edges == []:
                return 0, 0
            diameter = 0
            graph = defaultdict(list)
            deg = defaultdict(int)
            for u, v in edges:
                graph[u].append(v)
                graph[v].append(u)
                deg[u] += 1
                deg[v] += 1
            seen = set()
            leafs = [u for u in deg if deg[u] == 1]
            depth = defaultdict(int)
            while leafs != []:
                u = leafs.pop(0)
                if u in seen:
                    continue
                seen.add(u)
                for v in graph[u]:
                    if v in seen:
                        continue
                    diameter = max(diameter, depth[v] + depth[u] + 1)
                    depth[v] = max(depth[v], depth[u]+1)
                    deg[v] -= 1
                    if deg[v] == 1:
                        leafs.append(v)
            return max(depth.values()), diameter
        
        depth1, diameter1 = dfs(edges1)
        depth2, diameter2 = dfs(edges2)
        return max(depth1 + depth2 + 1, diameter1, diameter2)

提交代码评测得到:耗时3216ms,占用内存93.4MB。

标签:Diameter,3203,diameter,int,graph,After,depth,leafs,deg
From: https://blog.csdn.net/codename_cys/article/details/140083957

相关文章

  • Cobra - Flags are parsed after rootCmd.Execute()
     root.go:funcinit(){rootCmd.PersistentFlags().BoolVarP(&enableLogging,"log","l",true,"Logginginformation")fmt.Println("*************************",enableLogging)}funcExecute(){err:......
  • docker拉取镜像失败error pulling image configuration: download failed after attem
    最近很多朋友遇到docker拉取镜像失败的问题因为一些网络问题,无法访问docker官方镜像仓库,我们可以通过设置阿里云镜像加速器的方式解决该问题。解决方法:1.访问阿里云官网,并登录https://www.aliyun.com/2.搜索容器镜像服务3.点击立即开通4.根据提示免费开通个人版,开通......
  • IDEA报错:Cannot invoke(class=Package]sonListener,method=after,topic=BulkFileListe
    1.问题描述安装IDEA23年版本后创建.java文件失败并报错无法创建类无法解析模板"Class",措误消息:Cannotinvoke(class=Package]sonListener,method=after,topic=BulkFileListener)2.解决方式按如下图片检查以下设置2.1检查文件类型2.2检查文件和代码模板2.3检......
  • After Effects 2024 mac/win版:创意视效,梦想起航
    AfterEffects2024是一款引领视效革命的专业软件,汇聚了创意与技术的精华。作为Adobe推出的全新版本,它以其强大的视频处理和动画创作能力,成为从事设计和视频特技的机构,如电视台、动画制作公司、个人后期制作工作室以及多媒体工作室的得力助手。AdobeAfterEffects2024mac/win......
  • NG32031单片机串口初始化
    目录1.串口基础2.串口配置步骤3.N32G031串口初始化示例3.1开启时钟3.2 配置GPIO3.3 配置USART3.4 使能中断(如果需要)    3.5. 示例代码4.调试和验证5.注意事项6.额外功能NG32G031单片机的串口(UART)通常用于与外部设备或计算机进行串行通信。以下......
  • @AfterReturning和@After区别
    @AfterReturning和@After是SpringAOP(面向切面编程)中的两个重要注解,它们各自在方法执行的不同时间点执行特定的逻辑。以下是它们之间的主要区别:执行时机:@AfterReturning:在目标方法成功执行并返回结果之后执行。这意味着,只有当目标方法正常完成,没有抛出任何异常时,才会触发@After......
  • CF1192B Dynamic Diameter 题解
    思路静态\(\text{toptree}\)板子题。定义我们使用簇来表示树上的一个连通块。可以按照如下方式定义一个簇:一个簇可以表示为三元组\((u,v,E)\),其中\(u,v\)为树的节点,称为簇的界点,\(E\)为一个边的集合,表示该簇包含的边,路径\((u,v)\)称作簇路径。\(u,v\)分别为上界......
  • 深入学习 CSS 中的伪元素 ::before 和 ::after
    CSS伪元素用于为元素的指定部分设置样式,作为回顾,先来看下 Mozilla 开发者网站上的解释:伪元素是一个附加至选择器末的关键词,允许你对被选择元素的特定部分修改样式。例如 ::first-line 伪元素可用于更改段落首行文字的样式。可用的CSS伪元素不是很多,但是,作为前端工程师......
  • Python - Django - MySQL #need to add distinct() after select_related().distinct(
    所以这是ads/views.py还有ads/models.py、ads/forms、ads/urls.py和其他文件,但评分器抱怨的是这个views.py...检索到3806个HTML字符测试已完成:在页面顶部发现菜单栏搜索"HHGTTG_421717639962"时发现多个广告。您可能需要在views.py中的select_related().di......
  • DynamiCrafter: 腾讯开源,图片秒变动画大片的AI创意工具
    DynamiCrafter是一款由腾讯、北大等开发的图像动画工具。通过利用预训练的视频扩散先验,可以基于文本提示为开放域的静止图像添加动画效果。该工具支持高分辨率模型,提供更好的动态效果、更高的分辨率和更强的一致性。产品功能:动画生成:DynamiCrafter能够根据用户提供的文本......