做网站判多少年,c 做网站,工程项目建设网站,网站上做地图手机上显示Leetcode 3203. Find Minimum Diameter After Merging Two Trees 1. 解题思路2. 代码实现 题目链接#xff1a;3203. Find Minimum Diameter After Merging Two Trees
1. 解题思路
这一题的话算是一个拓扑树的题目#xff1f;总之就是从树的叶子节点不断向上遍历#xff…Leetcode 3203. Find Minimum Diameter After Merging Two Trees 1. 解题思路2. 代码实现 题目链接3203. Find Minimum Diameter After Merging Two Trees
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, 0diameter 0graph defaultdict(list)deg defaultdict(int)for u, v in edges:graph[u].append(v)graph[v].append(u)deg[u] 1deg[v] 1seen set()leafs [u for u in deg if deg[u] 1]depth defaultdict(int)while leafs ! []:u leafs.pop(0)if u in seen:continueseen.add(u)for v in graph[u]:if v in seen:continuediameter max(diameter, depth[v] depth[u] 1)depth[v] max(depth[v], depth[u]1)deg[v] - 1if deg[v] 1:leafs.append(v)return max(depth.values()), diameterdepth1, diameter1 dfs(edges1)depth2, diameter2 dfs(edges2)return max(depth1 depth2 1, diameter1, diameter2)提交代码评测得到耗时3216ms占用内存93.4MB。
