⚡️『重要结论』NC99 树的直径
树的直径
https://www.nowcoder.com/practice/a77b4f3d84bf4a7891519ffee9376df3?tpId=117&&tqId=37824&&companyId=665&rp=1&ru=/company/home/code/665&qru=/ta/job-code-high/question-ranking
- 参考自牛油：六娃lw
该题为求多叉树的直径、第二直径的问题。
前几天在牛客巅峰赛上遇到了，赛后主讲人讲了一个通用的思路。对于此类问题，我们需要构建图来做深度优先搜索。
- 首先，根据父子关系及边权重构建无向图；
- 然后，随机找一顶点，利用深度优先搜索找到距离该点最远的顶点remote。
- 最后，从remote顶点开始深度优先搜索找到最长路径，该路径即为直径。
同程旅行工作强度 20人发布
