Leetcode 1245:树的直径(超详细的解法!!!)
in leetcode with 0 comment

Leetcode 1245:树的直径(超详细的解法!!!)

in leetcode with 0 comment

给你这棵「无向树」,请你测算并返回它的「直径」:这棵树上最长简单路径的 边数

我们用一个由所有「边」组成的数组 edges 来表示一棵无向树,其中 edges[i] = [u, v] 表示节点 uv 之间的双向边。

树上的节点都已经用 {0, 1, ..., edges.length} 中的数做了标记,每个节点上的标记都是独一无二的。

示例 1:

输入:edges = [[0,1],[0,2]]
输出:2
解释:
这棵树上最长的路径是 1 - 0 - 2,边数为 2。

示例 2:

输入:edges = [[0,1],[1,2],[2,3],[1,4],[4,5]]
输出:4
解释: 
这棵树上最长的路径是 3 - 2 - 1 - 4 - 5,边数为 4。 

提示:

解题思路

这个问题和之前问题Leetcode 543:二叉树的直径(超详细的解法!!!)非常类似,所以这题我们依旧可以采用dfs来处理。

和之前问题不同的地方是该问题中是图的遍历(之前问题是树的遍历),所以我们需要求出每个节点周围所有最长路径中最长的两个(相当于之前问题中的lr),dfs的返回结果就是最长的那个路径加1(表示当前节点可以访问的最远距离)。

class Solution:
    def treeDiameter(self, edges: List[List[int]]) -> int:
        g, res = collections.defaultdict(list), 0
        for a, b in edges:
            g[a].append(b)
            g[b].append(a)

        def dfs(cur, pre):
            nonlocal res
            d1 = d2 = 0
            for i in g[cur]:
                if i != pre:
                    d = dfs(i, cur)
                    if d > d1:
                        d1, d2 = d, d1
                    elif d > d2:
                        d2 = d
            res = max(res, d1 + d2)
            return d1 + 1

        dfs(0, None)
        return res

这个问题还可以使用bfs来解。bfs的思路比较特殊,我们需要先通过一次bfs找到每个节点离它最远的距离,然后在这些最远的距离中找最远的那个(相当于找到了半径)并且记录端点(找到了直径的端点)。再通过直径的端点进行bfs找直径即可。例如

我们首先从0出发找到此时所有节点的最长距离3,并且此时最长距离的另一个端点是5。此时再从5出发找到我们的直径453)。

代码的写法上要比dfs复杂一些,我们需要开辟一个n大小(n表示节点个数)的数组记录每个节点可以到达的最远距离。

class Solution:
    def treeDiameter(self, edges: List[List[int]]) -> int:
        g, n = collections.defaultdict(list), 0
        for a, b in edges:
            g[a].append(b)
            g[b].append(a)
            n = max([n, a, b])
            
        def bfs(u):
            q, dis = [u], [-1] * (n + 1)
            dis[u] = 0

            while q:
                t = q.pop(0)
                for i in g[t]:
                    if dis[i] == -1:
                        q.append(i)
                        dis[i] = dis[t] + 1
            
            resDia, resId = 0, 0
            for i in range(n + 1):
                if dis[i] > resDia:
                    resDia, resId = dis[i], i
            return [resId, resDia]
        
        t1 = bfs(0)
        return bfs(t1[0])[1]

我将该问题的其他语言版本添加到了我的GitHub Leetcode

如有问题,希望大家指出!!!

「如果我的文章对你有很大帮助,那么不妨~!」

coordinate

谢谢老板O(∩_∩)O~

使用微信扫描二维码完成支付

Responses