# 多叉树的直径

![last modify](https://img.shields.io/static/v1?label=last%20modify\&message=2022-10-14%2014%3A59%3A33\&color=yellowgreen\&style=flat-square) [![](https://img.shields.io/static/v1?label=\&message=%E5%9B%B0%E9%9A%BE\&color=yellow\&style=flat-square)](https://imhuay.gitbook.io/studies/algorithms/..#困难) [![](https://img.shields.io/static/v1?label=\&message=%E7%89%9B%E5%AE%A2\&color=green\&style=flat-square)](https://imhuay.gitbook.io/studies/algorithms/..#牛客) [![](https://img.shields.io/static/v1?label=\&message=%E5%9B%BE\&color=blue\&style=flat-square)](https://imhuay.gitbook.io/studies/algorithms/..#图) [![](https://img.shields.io/static/v1?label=\&message=%E6%B7%B1%E5%BA%A6%E4%BC%98%E5%85%88%E6%90%9C%E7%B4%A2\&color=blue\&style=flat-square)](https://imhuay.gitbook.io/studies/algorithms/..#深度优先搜索)

> [多叉树的直径\_牛客题霸\_牛客网](https://www.nowcoder.com/practice/a77b4f3d84bf4a7891519ffee9376df3)

**问题简述**

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

**思路**

> 本题实际上是求无向无环图的最大直径；真正求 N 叉树直径的问题见 [N 叉树的直径 - 力扣（LeetCode）](https://leetcode-cn.com/problems/diameter-of-n-ary-tree/)

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

  > [无/有向图的最长路径-图的直径 - 知乎](https://zhuanlan.zhihu.com/p/44391252)
* 基于以上结论，可以得到算法：
* 从任意一点出发，DFS 找到最长路径的终点；
* 再从该终点出发，找到的最长路径即为整个图的最长直径；

<details>

<summary><strong>Python</strong></summary>

```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
```

</details>