一、基础树中最远的两个结点之间的距离被称为树的直径，连接这两点的路径被称为树的最长链（也称直径）二、两次遍历求直径1、从任意一个结点出发，通过bfs或者dfs对树进行一次遍历，求出与出发点距离最远的结点，记为p，这就是树的直径的一端2、从结点p出发，通过bfs和dfs对树再进行一次遍历，求出与p距离最远的结点，记为q3、那么p到q的路径就是树的一条直径，因为p一定是直径的一端，否则总能找到一条更长的链。在第二步遍历过程中，可以记录下来每个点第一次被访问时的前驱节点，最后从q回溯到p即可得到直
ACM知识（硬货）
2024-01-24
45 点赞
0 评论
68 浏览
