• Leetcode 3203. Find Minimum Diameter After Merging Two Trees
  • 1. 解題思路
  • 2. 代碼實(shí)現(xiàn)

• 題目鏈接：3203. Find Minimum Diameter After Merging Two Trees

1. 解題思路

這一題的話算是一個(gè)拓?fù)錁涞念}目？總之就是從樹的葉子節(jié)點(diǎn)不斷向上遍歷，不斷地刪除已訪問的葉子節(jié)點(diǎn)，并加入更新之后的新的葉子節(jié)點(diǎn)，這樣我們就能得到樹的最大深度，然后在遍歷過程中我們考察其任意節(jié)點(diǎn)上的當(dāng)前深度和已有深度的和的最大值，即為經(jīng)過該節(jié)點(diǎn)的最大路徑長(zhǎng)度，遍歷整張圖，我們即刻獲得整個(gè)樹的深度和diameter。然后，我們要連接兩個(gè)圖的話，能夠獲得的最大路徑長(zhǎng)度就是兩個(gè)圖的深度之和加一。

由此，我們即可完成這道題目了。

2. 代碼實(shí)現(xiàn)

給出python代碼實(shí)現(xiàn)如下：

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)

提交代碼評(píng)測(cè)得到：耗時(shí)3216ms，占用內(nèi)存93.4MB。