树直径算法O(N)时间复杂度原理讲解图文

1. 最终统计: 遍历每一个点 i。比较 i 到 x 的距离(dx[i])和 i 到 y 的距离(dis[i])。哪个更大，那个端点（x 或 y）就是距离 i 最远的点。2.核心原理: 为什么是 O(N)? 这道题之所以能在 O(N) 解决，是因为它不需要对每个点做一次 BFS（那样是 O(N²)），而是利用了数学性质。定理: 在一个树形结构中，对于任意节点 u，距离它最远的节点 v，一定满足 v 是树直径的两个端点之一。通俗解释: 想象这棵树是一根绳子结构，直径就是这根绳子拉直后最长的主干（从 x 到 y）。树上的其他部分都是从这个主干上分叉出去的“短树枝”。如果你站在任意一个点上，想要走得最远，你肯定要先走到主干上，然后往主干的两头走。既然x和y是主干的两头，那么最远的路必然是通向 x 或者通向 y 的。

这是一份讲解树直径线性时间复杂度算法的教程图文内容，上方首先列出最终统计的步骤：遍历每个点i，分别比较i到端点x和i到端点y的距离，数值更大的对应的端点即为距离i最远的点。接下来讲解核心原理“为何该算法时间复杂度为O(N)”，中间插入了一张树木横截面的素材示意图，标注出了髓、心材、髓射线、生长轮、边材、形成层、内树皮、外树皮等树木结构。下方文字说明该算法无需对每个点执行BFS，否则时间复杂度为O(N²)，而是利用了树形结构的数学性质，给出对应定理：在树形结构中，任意节点u的最远节点v一定是树直径的两个端点之一，还给出通俗解释，将树类比为绳子，直径是绳子拉直后的最长主干，其余部分都是主干分叉出的短树枝，站在任意点要走最远必然先到达主干再向两端行进，因此最远路径一定通向直径的两个端点x或y之一，图片右下角有知乎用户@Keynary的署名，树木示意图右上角带有Shutterstock的版权水印。

该内容的RSS来源为X.com的hsn-bot账号，内容本身的原创作者为知乎用户@Keynary，是其创作的算法教学内容，其中使用的树木横截面示意图来自商用素材库Shutterstock。