能，两次BFS/DFS一定能找到树的直径，前提是图是无环连通无向图；第一次从任一节点出发找到最远点（直径一端），第二次从该点出发找到最远距离即为直径长度。
两次BFS/DFS一定能找到树的直径吗
能，但前提是图必须是无环连通无向图（即一棵真正的树）。对任意树，从任一节点出发做一次BFS或DFS，到达的最远节点一定是直径的一个端点；再从该端点出发做第二次BFS/DFS，最远距离就是直径长度。这个性质成立的关键在于树的唯一路径性——任意两点间只有一条简单路径。
常见错误现象：dist[0]初始化为0但没清零全局数组，导致第二次遍历时残留上次结果；或者误把有向图、带环图当作树来跑，得到错误结果。
- 务必确认输入是连通且无环的——可通过边数是否等于
n-1+ DFS遍历节点数是否为n双重验证 - 使用邻接表而非邻接矩阵，避免
O(n²)空间和超时（尤其n > 1e5时） - BFS比DFS更稳妥：避免递归栈溢出，且天然支持记录路径（若还需输出直径上的点）
用BFS实现时怎么记录最远节点和距离
核心是维护一个dist数组和一个prev数组（可选），每次BFS结束后扫描dist找最大值及其下标。不需要额外标记“是否为直径端点”，只需两次调用：
int bfs(int start, vector<int>& dist, const vector<vector<int>>& g) {
fill(dist.begin(), dist.end(), -1);
queue<int> q;
dist[start] = 0;
q.push(start);
while (!q.empty()) {
int u = q.front(); q.pop();
for (int v : g[u]) {
if (dist[v] == -1) {
dist[v] = dist[u] + 1;
q.push(v);
}
}
}
// 返回最远节点编号
return max_element(dist.begin(), dist.end()) - dist.begin();
}
注意：max_element返回迭代器，需减去begin()得下标；dist必须用-1初始化（不能用0），否则无法区分未访问节点。
立即学习“C++免费学习笔记（深入）”；
- 若树边有权（正权），必须换用Dijkstra或DFS，BFS不再适用
- 如果只需求直径长度，第二次BFS后直接取
*max_element(dist.begin(), dist.end())即可 - 想同时得到两个端点？第一次BFS返回
u，第二次从u出发BFS返回v，则(u, v)就是一对直径端点
DFS递归写法容易爆栈或写错边界吗
容易。典型坑是忘记传引用导致反复拷贝dist，或递归终止条件漏判visited造成死循环。DFS更适合边权非1的情况，但纯求无权树直径时，BFS更直白可靠。
若坚持用DFS，推荐用栈模拟或加static变量控制深度——但不推荐。真实项目中，n > 1e4就该警惕递归深度。
- 必须用
vector<bool> vis</bool>显式标记，不能只靠父节点判断（树无环但邻接表含反向边） - 参数列表里传
parent比用vis稍快，但逻辑易错：“跳过父节点”要写在循环开头，不是结尾 - 返回值建议只返回最大深度，直径长度由上层组合两个子树深度计算——这是树形DP思路，适合拓展（如求最长链、带权情况）
LeetCode 1245题或自测时答案不对，可能卡在哪
大概率是建图错了。C++里常见错误包括：vector<vector>> g(n)</vector>但节点编号从1开始，导致g[0]永远空；或者读入边后只加了一次单向边（g[u].push_back(v)但漏了g[v].push_back(u)）。
另一个隐蔽问题是：题目给的是“树的边列表”，但你当成“有向树”处理，没建无向图。
- 打印前10个
g[i].size()看看是否全为0——如果是，说明建图失败 - 用小样例手算：3个节点边为
[[1,2],[2,3]]，直径应为2；若输出1，基本确定是单向建图或起点固定成0没适配输入编号 - 多组测试用例下，记得每次清空
g和重置dist大小——别复用旧vector容量
树的直径本质是两遍最远点搜索，算法本身极简；真正耗时间的，往往是建图、索引偏移、边界初始化这些“非算法”细节。
