很多人第一次认真研究“树的直径”是在算法竞赛的进阶训练里又或者是在某个大厂面试的代码轮次中突然被问到。我当时则是在调一个分布式任务调度器的竞态问题排到半夜发现瓶颈根本不是锁而是一棵依赖树里两个最远节点之间的链路时延被低估了——那一瞬间脑子蹦出来的第一个念头就是这不就是树的直径么。树直径这个看似简单的概念在现实系统里其实非常常见只是大多数人在校招刷题之外很少把它当作工程工具来用。这篇内容不打算给你堆一堆背诵模板而是想从“为什么能这么做”“什么时候不能这么做”“实际代码里有哪些坑”三个角度把树的直径讲透。无论你是备考、写竞赛题还是想在真实项目中用它做链路分析、网络拓扑评估、依赖层级优化都能从中拿到可以直接落地的思路。1. 树的直径到底在求什么定义、直觉与典型应用场景树的直径并不是一个很难理解的概念。简单说在一棵无权树或带权树中任意选出两个节点它们之间的简单路径长度可能会各不相同。树的直径就是这些路径中长度最大的那一条或者说那个最长距离的值。这里的“长度”有两种度量方式按边数或者按节点数。按边数的时候一条边算1按节点数的时候一个节点算1。两种口径在纯树上只相差一个常数但如果你的树里存在权值或者你求的是“路径上的节点数量”而不是“边数”那就要非常小心。实际工程里更多使用的是边权版本因为网络链路时延、依赖层级成本、地图导航路程这些场景天然是以边为单位计算的。让我用几个例子帮助建立直觉内容分发网络里叶子节点是各缓存节点根是源站。你想知道“在最好的情况下最远的两个缓存节点之间的传输延迟是多少”这就是树的直径。编译系统里目标文件之间构成依赖图。如果依赖关系形成一棵树那么两个相隔最远的目标文件之间的编译链路长度就是树的直径。这个值决定了一次全量构建里最长串行路径能有多长。社交关系里如果忽略非树结构割边等两个人之间的最大最短距离也接近树的直径。某些六度分隔理论测的就是类似指标。直觉上的最大误区是认为树的直径一定穿过根节点。不对它根本不关心根在第一遍遍历时是谁。树中任何两点之间只有一条简单路径直径路径是“最长的两点间简单路径”它可能在树的某个分支内部就完成了根本不需要经过你指定的那个根。这也是为什么后面介绍的方法不是从指定根直接向下搜而是先从任意点找最远点再从这个最远点搜一遍——目的就是让直径的两个端点自己“浮出水面”。如果你还没做过任何树相关的题可以把这棵树的邻接表想象成一张无向图N个节点、N-1条边并且保证连通。每个节点只有一个父节点但可以有很多子节点。直径这条路径就是图上一对距离最远的点集的路径。2. 两次遍历方法的核心证明为什么最远点一定是直径端点2.1 方法描述树上求直径最经典、最简单的算法就是两次搜索搜索可以选BFS或DFS效果一样从任意节点 U 出发用 BFS 或 DFS 找到离 U 最远的节点记为 A。再从 A 出发用同样的方法找到离 A 最远的节点记为 B。从 A 到 B 的距离就是树的直径。我第一次看到这个算法时觉得也太作弊了——凭什么只搜两遍就能直接干出全局最大值这个结论并不是显然的它依赖于树的一个特殊性质树上任意两点路径唯一。这个性质直接导致了以下的证明逻辑可以成立。2.2 正确性证明的通俗版本设直径的两个端点分别为 X 和 Y真正的直径为 D(X, Y)。第一步我们是从任意节点 U 出发找到了最远节点 A。要证明的是A 必然是 X 或 Y 中的一个或者至少A 到某个直径端点的距离不会小于真正的直径。这里我用一个反证式的通俗做法来解释。假设 U 出发的最远点是 A且 A 既不是 X 也不是 Y。考虑 U 到 A 的路径与直径 X-Y 的路径的关系。由于树中路径唯一两条路径要么完全不重叠要么有一段公共部分。如果两条路径完全不相交中间通过某个节点 M 相连那么从 U 到 A 的距离是 U-M-A。既然 A 是最远点那么从 U 出发走到 X 或 Y 的距离都不会大于 U-M-A。但这会导致 X-M-A 或 Y-M-A 的距离比真正的直径更长矛盾。如果两条路径相交于某个节点 C那么 U 到 A 经过 C。由于 A 是最远点所以 U-C-A 的距离不小于 U-C-X 和 U-C-Y。整理不等式容易推出 A 到 Y 或 A 到 X 的距离会达到或超过 D(X,Y)于是 A 必须被认定为直径的一个端点或者是等价的最远点。这个证明并不需要背下来但你一定要理解那棵树的“路径唯一性”在整个论证里扮演的角色。因为只有路径唯一两条路径的交叠关系才是线性的你才能用路径上的距离做加减比较。若是在一般图里两点之间可能有多种走法最短路径最远点的性质就会失效这个方法直接不成立。2.3 常见误解澄清为什么不能只从根节点搜一遍很多人会问那我把根定在节点1直接DFS从根找叶子最远点再从这个叶子出发找最远点不也一样吗实际上这也是可行的但你要理解根节点只是第一遍搜索的“任意起点”之一并不是什么特殊起点。“从根节点开始的第一次搜索”其实就等价于“从任意节点 U 开始的第一次搜索”所以只要你的搜索起点是任意点那么从任何节点开始都一样包括用1号节点。千万不要认为必须从“中心/根”出发才能找到直径。另一个常见误解是两次搜索第一次找到的A是树的“一个端点”那么第二次搜索的结果一定是另一个端点。这句话其实也基本正确但前提是树中所有边权非负。如果你遇到负权边这个方法失效要用树形DP。这个在下一节会详细对比。3. 代码落地两次DFS/BFS与树形DP的完整实现与选型对比3.1 两次DFS实现的模板边权为1我平时使用的是C邻接表写法。如果边权均为1也就是普通无权树代码可以写得非常精简。#include bits/stdc.h using namespace std; const int N 100005; vectorint g[N]; int dist[N]; int farNode, maxDist; void dfs(int u, int fa) { if (dist[u] maxDist) { maxDist dist[u]; farNode u; } for (int v : g[u]) { if (v fa) continue; dist[v] dist[u] 1; dfs(v, u); } } int diameter(int n) { int s 1; // 任意起点 dist[s] 0; maxDist -1; dfs(s, 0); int a farNode; dist[a] 0; maxDist -1; dfs(a, 0); return maxDist; // 直径长度边数 }这个实现非常简单。“fa”参数用来避免走回父节点这本质上就是用特殊父节点代替visited数组因为树是无环的一次迭代就可以覆盖所有节点。每次递归更新dist数组并在递归过程中记录当前最远节点。这里有个细节如果边数非常多比如N达到1e6DFS递归会在某些评测系统上爆栈。这时要么用#pragma comment(linker, /STACK:16777216)之类的栈调整要么改用BFS的queue实现要么自己维护一个显式栈。第二个选项最稳。3.2 两次BFS实现模板处理带权边如果带权比如边权代表时延那就要用BFS/DFS的加权版本。但需要强调这个“加权BFS”成立的前提是所有权值都非负。如果所有边权都是正的或0可以将普通BFS替换为基于优先队列的Dijkstra算法。因为树的特殊结构即使有边权只要非负仍然可以从任意点出发用Dijkstra求最远点再以最远点为源点做第二次Dijkstra。#include bits/stdc.h using namespace std; const int N 100005; struct Edge { int to; long long w; }; vectorEdge g[N]; long long dist[N]; int farNode; void dijkstra(int s) { memset(dist, 0x3f, sizeof(dist)); dist[s] 0; priority_queuepairlong long, int, vectorpairlong long, int, greaterpairlong long, int pq; pq.push({0, s}); long long maxD -1; while (!pq.empty()) { auto [d, u] pq.top(); pq.pop(); if (d ! dist[u]) continue; if (d maxD) { maxD d; farNode u; } for (auto e : g[u]) { if (dist[e.to] dist[u] e.w) { dist[e.to] dist[u] e.w; pq.push({dist[e.to], e.to}); } } } } long long diameter(int n) { dijkstra(1); int a farNode; dijkstra(a); return dist[farNode]; }这里的优先队列其实相当于“加权BFS”的经典做法。有人会质疑在树上用Dijkstra是不是炮打蚊子其实不是。树只是没有环但带权树的最远点性质仍然依赖非负权用Dijkstra做保证是稳妥的选择。3.3 树形DP方法一次DFS就能解决且支持负权边如果树带负权边两次遍历的方法就会彻底失效。原因是第一遍找最远点的过程在负权环境下不能再保证“最远点位于某条直径端点”这时需要换个思路。一种标准做法是树形DP在一次DFS中对每个节点维护两个值dp1[u]从u出发向子树方向走能到达的最远距离。dp2[u]从u出发向子树方向走的次远距离。当处理完u的所有孩子v之后dp1[u] max(dp1[v] w(u,v))同时维护一个候选答案 ans max(ans, dp1[u] dp2[u])。这里的dp2[u]是第二大的dp1[v] w(u,v)值。最终ans就是直径。这个DP的妙处在于它会枚举“直径路径经过的某个节点u”并把这条路径拆成两个方向的最长链相加。这样即使边走负权甚至边权有负有正也能正常处理因为你计算的是真实路径和而不是依赖“最远点单调性”。#include bits/stdc.h using namespace std; using ll long long; const ll INF 1e18; struct Edge { int to; ll w; }; vectorEdge g[100005]; ll ans -INF; void dfs(int u, int fa) { ll max1 0, max2 0; // 面向普通题目初始化为0代表可以不往子树走 for (auto e : g[u]) { int v e.to; if (v fa) continue; dfs(v, u); ll val max1_for_subtree(v, 0); // 这里示意实际要把dp传出来 } }上面的代码断了一截为了演示方便我给一个完整可运行的独立版本#include bits/stdc.h using namespace std; const int N 100005; struct Edge { int to; long long w; }; vectorEdge g[N]; long long ans -1e18; long long dfs(int u, int fa) { long long max1 0, max2 0; for (auto e : g[u]) { int v e.to; if (v fa) continue; long long child dfs(v, u) e.w; if (child max1) { max2 max1; max1 child; } else if (child max2) { max2 child; } } ans max(ans, max1 max2); return max1; } int main() { int n 5; // 示例树边可自行替换 g[1].push_back({2, 5}); g[2].push_back({1, 5}); g[2].push_back({3, -2}); g[3].push_back({2, -2}); g[2].push_back({4, 1}); g[4].push_back({2, 1}); dfs(1, 0); cout ans endl; return 0; }注意这里我把max1初始化为0这意味着每个节点可以选择“不向任何子树延伸”这对应直径路径至少经过一个节点的情况。如果题目要求直径路径必须至少经过一条边则max1和max2初始化为负无穷会更严谨一点但大多数题目默认节点本身有长度或允许单点作为路径所以初始化为0通常是安全且方便的。3.4 两种方法的选型对比维度两次遍历法树形DP法遍历次数两次BFS/DFS/Dijkstra一次DFS理论基础最远点到最远点依赖非负权每个节点拆两条最长链支持负权边不支持支持代码复杂度低中空间占用需要dist数组只需要返回值和ans返回信息只能拿到长度难以追溯路径同样只能拿到长度追溯路径需要额外数组推荐场景无权树、非负权树快速实现有权树、负权树、需要特殊链合并的情况大多数情况下我强烈建议学会树形DP因为它的适用面更广而且一次遍历的代码实际更符合“树的递归结构”的自然思考方式。但很多竞赛题喜欢直接考察两次DFS因为它的结论更巧妙证明更精彩所以两种都应该掌握。4. 实战中必须处理的边界条件与踩坑记录4.1 只有1个节点或空树的边界如果树只有1个节点没有边直径是多少按边数算答案是0。按节点数算答案是1。这两种口径都常见处理不好会在第一题就翻车。我建议写一个专门处理n1的早退逻辑直接返回0按边数或返回n。在两次遍历法中如果n1第一次dfs会把farNode设为1第二次dfs距离也是0所以代码天然返回0看上去不会崩但如果你的代码在第二次dfs里读取dist[farNode]且同时把ans初始化为-1那返回值会是-1这就错了。这个问题很隐蔽我见过不少人答案差1或差2其实根子就在初始化。4.2 输入是“有向边”还是“无向边”的陷阱树在定义上是无向图但很多场景的数据输入会用父子关系、父节点数组等方式给出。如果你拿到的是一个父节点数组比如par[i]表示i的父节点要注意这不一定代表树的根就是0或1。更常见的陷阱是你按“有向边”建邻接表结果第二次搜索时根本没有办法从叶子走回父节点导致永远找不到真正的端点。我的建议是遇到这类题目第一时间在草稿纸上明确“这里是树是无向边双向建边”。尤其是用vector存储邻接表的时候每次读取(u,v)要push_back两次。但如果输入明确说明是有向边或者父节点数组那也别盲目双向建边因为父子关系是有向的这时候构造的是有根树。解决方法是先确定根然后建单向边如果你需要从任意节点出发搜索那就仍然需要双向边否则搜索范围被永远限制在子树内。4.3 递归爆栈与性能优化当N超过1e5时DFS递归深度可能达到树的深度最坏情况下是一条链递归深度达到N那么即便在Unix/Linux上开启大栈也可能遇到栈溢出。这在实际比赛或大项目中都会头疼。解决办法有两种使用BFS因为BFS不需要递归栈深度。自己实现一个显式栈的DFS把所有状态存到vector里。BFS版本其实和DFS逻辑几乎一模一样只是把递归换成了队列。对于两次遍历法我推荐BFS实现因为它省心。尤其当边权全为1时普通队列就能完成最远点搜索如果带非负权才需要优先队列。这里再提一下“路径回溯”问题。如果你不仅需要树的直径的长度还需要输出这条最长路径上的具体节点那两次遍历法比较方便因为你可以在第二次搜索过程中记录每个节点的父节点然后从终点B回溯到起点A。树形DP如果想输出路径需要额外记录每个节点合并时的方向相对麻烦一些。4.4 负权边情况下的错误结果负权边是我看过最多人踩的坑因为题目不会明说“边权可能为负”。如果你在带负权树上使用两次DFS第一次从任意点找最远点可能找到一个并不是直径端点的节点第二次搜索结果就完全错了。举一个简单例子一条链上三个节点中间节点到两边节点权值都是正数但某条边改为负直接让第一次搜索被负权误导。这时候你只能用树形DP或基于每个节点采用最长路径动态规划的方法。这也是为什么我前文那么强调要理解DP方法它并不依赖“最远点”性质而是对每个节点统计最长链和次长链从根本上规避了负权问题。4.5 多棵直径的计数问题两遍DFS可以正常求出直径长度但如果题目要求统计“有几条不同的直径路径”事情就变了。原因是两次DFS只能找到一条路径通常对应的是一条。要统计直径数量通常的做法还是树形DP基础上额外维护每个节点合并时的路径计数或者做二次DFS换根复杂度仍然是O(N)。这个需求并不常出现在基础题目中但在一些综合性题目里比如“找出所有最长路径的交点”“判断是否所有最长路径经过同一点”时会用到。我的经验是先把不含计数的标准DP吃透再加上一个计数数组不过这块内容很容易写乱最好在纸上先推一阵再动笔。5. 我自己实际用过的优化思路与变体5.1 多次查询LCA 距离公式树的直径如果只是一次静态查询那两遍DFS就够了。但如果一棵树需要支持多次询问“任意两点的距离”且树是静态的那么可以考虑预处理LCA。因为在树中dist(u,v) depth[u] depth[v] - 2 * depth[lca(u,v)]。预处理出每个节点的深度和LCA后每次查询O(log N)。这看起来和直径无关但结合直径使用非常微妙。例如你要求“所有直径路径的公共区间”或“添加一条边后使得最长路径最小化”就需要快速计算任意两点的距离这本质上是对直径的增强操作。5.2 动态加边场景下的直径维护如果一棵树允许动态插入叶子节点并且你要持续维护当前树的直径长度直接每次两遍DFS显然不可行。一个常见的做法是记录当前直径的两个端点A和B。每次插入一个节点u时新直径只可能是以下情况之一原本的直径不变u到A的距离u到B的距离取三者最大值即可复杂度O(1)每次。这个结论基于树的直径端点性质在树上动态添加叶子时直径端点集合要么不变要么由新叶子替换其中一个端点。这个技巧在模拟最长链路、在线增量构建虚拟网络时非常有用。我曾在某个某跨平台系统的网络拓扑模拟项目里用过它效果理想。5.3 把树的直径用到业务链路评估中在实际工程里我很少直接把“求出直径”写成一个工具函数就结束更多是作为一个子步骤来评估某种“最坏情况”。比如在消息队列的层级树中计算最大扇出链路时先求出树的直径再结合各节点单点耗时估算端到端最大延迟。这种思路听着简单但确实能暴露很多压测中不容易发现的瓶颈节点。值得一提的坑是很多生产环境里的“依赖树”并不真的是树——它们往往是带环的图只是你在某个快照里把它简化成了树。在这种前提下用树的直径算法之前先做环检测要好得多否则结果没有意义。我吃过这个亏第一次给某模块算直径时没有检测环结果算出来一条路径居然比实际长很多排查了半天才发现是图里有一条隐性的环。5.4 对边权为负、但为森林的情况如何处理如果给你的不是一棵树而是一个森林即多个连通分量但每个分量无环那么“森林的直径”一般定义为各棵树直径的最大值。处理方式很简单对每个连通分量分别求直径取最大值。如果边权有负就用树形DP在每个分量内部跑最后比较。有一种特殊情况是允许在不同分量之间加一条边把它们连通问加边后的新直径最小值。这就变成了一个经典优化问题通常可以找出每棵树的“半径”作为代表点连接两个代表点可以最小化最大直径。这类题目已经不是单纯的树的直径而是直径重心的混合应用不过理解了基本模型后改代码并不难。6. 调试树的直径时的实用排查手册写这个部分是因为我见过太多人代码思路对却被一些奇怪原因卡住。以下按排查顺序列出高频原因先确认是不是树。输出节点数和边数如果N个节点却给了N条边多半不是树有可能是基环树或者图此时树的直径概念就不适用。再确认是不是无向图。如果是无向图双向建边是必须的。单向建边会导致第一次搜索只能覆盖一部分节点。检查dist数组的类型。边权可能很大如果总距离超过int上限必须用long long。我见过因为int溢出导致负距离、然后比较出错的情况。检查DFS里是否跳过了父节点。如果一个节点的邻接表里包含父向量但没有跳过父节点就会无限递归。虽然树无环但双向建边后邻接表天然有“回边”必须用fa参数规避。测试极小规模图。用n2、n3的单链测试手动算一遍距离并与程序输出对比可以快速暴露初始化和口径问题。对于树形DP确认每个节点返回的值是“向子树方向的最远距离”而不是“全局最远距离”。很多初学者在这搞混导致合并时重复计算。如果答案总是比预期大2倍基本是建图时不小心重复插入了同一条边或者把无向图的双向插入当成两个独立节点各插一条导致实际距离翻倍。通常检查一下邻接表的大小就知道。如果要求节点数而非边数记得答案加1或减1。按边数求得直径是5按节点数求就是6。口径统一很重要我见过有人题面明明让输出节点数代码用的是边数最后差1分。7. 最后再分享一个小技巧我一般写树的直径时不喜欢把dist数组暴露给外部。更常用的做法是封装一个函数pairint,int farthest(int s, vectorvectorpairint,long long g, long long maxDist)它返回最远节点编号和距离两次调用即可得到直径。这样一个函数可以复用到很多题里包括求重心、求半径、求最长公共路径等。另外如果你在评测平台上遇到“递归爆栈”但又不想换成BFS有一个简单的临时方案在main函数开头加一段动态调整栈空间的代码。例如Windows下的Visual C可以_resetstkoflwGCC下可以#include sys/resource.h在main里调用setrlimit提升栈空间。这个操作的兼容性一般但比赛环境通常可用。如果你长期写算法题我建议还是养成“非递归优先”的习惯毕竟你永远不知道题目的数据范围会藏多深。树的直径看起来只是个基础知识点但它的两种解法背后是两种完全不同的思考模式一种利用图性质做两次贪心遍历一种利用路径拆分做树形DP。后者才是真正能迁移到复杂问题里的能力。希望你看完这篇文章不只是多背了一个模板而是能自己在遇到问题时判断出该用哪种方案并避开那些藏在边界的坑。