多叉树的直径

多叉树的直径_牛客题霸_牛客网

问题简述

给定一棵多叉树，求出这棵树的直径，即树上最远两点的距离。
包含n个结点，n-1条边的连通图称为树。

思路

本题实际上是求无向无环图的最大直径；真正求 N 叉树直径的问题见 N 叉树的直径 - 力扣（LeetCode）

• 首先可以证明：假设最长直径为 s->t，那么从任意节点（记 m） DFS 得到的最深路径，其结束顶点必是 s 或 t；

  无/有向图的最长路径-图的直径 - 知乎

• 基于以上结论，可以得到算法：

• 从任意一点出发，DFS 找到最长路径的终点；

• 再从该终点出发，找到的最长路径即为整个图的最长直径；

Python

class Solution:
    def solve(self , n: int, Tree_edge: List[Interval], Edge_value: List[int]) -> int:
        from collections import defaultdict
        
        # 利用字典构造无向图
        g = defaultdict(list)
        for i in range(n - 1):
            x, y, v = Tree_edge[i].start, Tree_edge[i].end, Edge_value[i]
            g[x].append([y, v])
            g[y].append([x, v])
        
        def dfs(x, parent, cur_dist):
            mx_id, mx_dist = x, cur_dist
            for sub, v in g[x]:
                if sub != parent:  # 排除父节点
                    i, d = dfs(sub, x, cur_dist + v)
                    if d > mx_dist:
                        mx_id, mx_dist = i, d
            return mx_id, mx_dist
        
        i, _ = dfs(0, -1, 0)
        _, r = dfs(i, -1, 0)
        return r