问题引入
在树形结构中，”树的中心”是指使得到所有其他节点的最远距离最小的节点（可以有一个或两个中心）。与”树的重心”（使最大子树节点数最小）不同，中心关注的是距离度量。求树的中心需要先理解树的直径——树中最长的一条简单路径。本文用Java实现两次DFS求直径、换根DP求每个节点最远距离，最终定位树的中心，并扩展到树的半径与偏心距概念。
算法原理
树的直径
树的直径可通过两次DFS（或BFS）求得：
1. 从任意节点 u 出发，找到最远的节点 v
2. 从 v 出发，找到最远的节点 w
3. 路径 v-w 即为树的直径
证明：设直径为 a-b。若第一次DFS从任意点出发到达的最远点不是 a 或 b，则可通过三角不等式导出矛盾。
换根DP求所有节点最远距离
若仅求直径，两次DFS足够。但要找树的中心，需知道每个节点到所有其他节点的最远距离（偏心距）。换根DP通过两次遍历优雅解决：
第一次DFS（自底向上）：down[u] 表示从 u 向下走的最长距离（到子树中最远叶子的距离）。
down[u] = max(down[v] + w(u,v)) for all child v of u
第二次DFS（自顶向下）：up[u] 表示从 u 向上走（经过父节点）的最长距离。对于 u 的子节点 v：
up[v] = max(up[u], 次大down值 + w(u,parent)) + w(u,v)
节点 u 的偏心距为 max(down[u], up[u])，偏心距最小的节点即为树的中心。
Java完整实现
import java.util.*;
/**
* 树的中心求解：直径 + 换根动态规划
*/
public class TreeCenter {
static class Edge {
int to, weight;
Edge(int to, int weight) {
this.to = to;
this.weight = weight;
}
}
private List<Edge>[] graph;
private int n;
private int[] down; // 向下的最长距离
private int[] down2; // 向下的次长距离
private int[] up; // 向上的最长距离
private int[] parent; // 记录父节点
private int[] parentEdgeWeight;
public TreeCenter(int n) {
this.n = n;
graph = new ArrayList[n];
for (int i = 0; i < n; i++) graph[i] = new ArrayList<>();
down = new int[n];
down2 = new int[n];
up = new int[n];
parent = new int[n];
parentEdgeWeight = new int[n];
}
public void addEdge(int u, int v, int w) {
graph[u].add(new Edge(v, w));
graph[v].add(new Edge(u, w));
}
/**
* 第一次DFS：计算down值（自底向上）
*/
private void dfs1(int u, int p) {
parent[u] = p;
down[u] = 0;
down2[u] = 0;
for (Edge e : graph[u]) {
int v = e.to;
if (v == p) continue;
parentEdgeWeight[v] = e.weight;
dfs1(v, u);
int dist = down[v] + e.weight;
if (dist > down[u]) {
down2[u] = down[u];
down[u] = dist;
} else if (dist > down2[u]) {
down2[u] = dist;
}
}
}
/**
* 第二次DFS：计算up值（自顶向下）
*/
private void dfs2(int u, int p) {
for (Edge e : graph[u]) {
int v = e.to;
if (v == p) continue;
// up[v] 来自两部分：up[u]（继续向上）或 u 的down（转向另一子树）
int useDown = (down[u] == down[v] + e.weight) ? down2[u] : down[u];
up[v] = Math.max(up[u], useDown) + e.weight;
dfs2(v, u);
}
}
/**
* 求树的中心
* @return 中心节点列表（一个或两个）
*/
public List<Integer> findCenter() {
dfs1(0, -1);
dfs2(0, -1);
int minEccentricity = Integer.MAX_VALUE;
List<Integer> centers = new ArrayList<>();
for (int i = 0; i < n; i++) {
int ecc = Math.max(down[i], up[i]);
if (ecc < minEccentricity) {
minEccentricity = ecc;
centers.clear();
centers.add(i);
} else if (ecc == minEccentricity) {
centers.add(i);
}
}
return centers;
}
/**
* 求树的直径（两次DFS/BFS法）
* @return 直径长度
*/
public int findDiameter() {
int[] dist = bfs(0);
int farNode = 0;
for (int i = 1; i < n; i++) {
if (dist[i] > dist[farNode]) farNode = i;
}
dist = bfs(farNode);
int diameter = 0;
for (int d : dist) diameter = Math.max(diameter, d);
return diameter;
}
/**
* BFS求单源最短路（树中即为距离）
*/
private int[] bfs(int start) {
int[] dist = new int[n];
Arrays.fill(dist, -1);
Queue<Integer> q = new LinkedList<>();
q.offer(start);
dist[start] = 0;
while (!q.isEmpty()) {
int u = q.poll();
for (Edge e : graph[u]) {
int v = e.to;
if (dist[v] == -1) {
dist[v] = dist[u] + e.weight;
q.offer(v);
}
}
}
return dist;
}
/**
* 打印每个节点的偏心距
*/
public void printEccentricities() {
System.out.println("节点信息:");
System.out.println("节点\tdown\tup\t偏心距");
for (int i = 0; i < n; i++) {
int ecc = Math.max(down[i], up[i]);
System.out.printf("%d\t%d\t%d\t%d%n", i, down[i], up[i], ecc);
}
}
/**
* 辅助方法：构建示例树
* 0
* /|\
* 1 2 3
* / \
* 4 5
* /
* 6
*/
public static TreeCenter createExample() {
TreeCenter tree = new TreeCenter(7);
tree.addEdge(0, 1, 1);
tree.addEdge(0, 2, 1);
tree.addEdge(0, 3, 1);
tree.addEdge(1, 4, 1);
tree.addEdge(3, 5, 1);
tree.addEdge(4, 6, 1);
return tree;
}
public static void main(String[] args) {
TreeCenter tree = createExample();
System.out.println("=== 树的中心求解演示 ===\n");
int diameter = tree.findDiameter();
System.out.println("树的直径: " + diameter);
List<Integer> centers = tree.findCenter();
System.out.println("树的中心: " + centers);
tree.printEccentricities();
// 测试权重不同的树
System.out.println("\n=== 带权树测试 ===");
TreeCenter weightedTree = new TreeCenter(5);
weightedTree.addEdge(0, 1, 3);
weightedTree.addEdge(0, 2, 1);
weightedTree.addEdge(2, 3, 2);
weightedTree.addEdge(2, 4, 4);
System.out.println("带权树直径: " + weightedTree.findDiameter());
System.out.println("带权树中心: " + weightedTree.findCenter());
weightedTree.printEccentricities();
}
}
复杂度分析
| 操作 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 求直径（两次BFS） | O(n) | O(n) |
| 换根DP（两次DFS） | O(n) | O(n) |
| 整体求中心 | O(n) | O(n) |
所有操作均为线性时间，这是因为树没有环，每个边和节点仅被访问常数次。
扩展思考
- 树的半径：树的半径等于直径的一半（向上取整），即中心节点的偏心距。半径与直径满足
diameter ≤ 2 × radius。 - 多中心情况：当直径长度为奇数时，树有两个中心（直径中点两侧各一个）；为偶数时有一个中心。
- 动态树维护：若树需要支持加边/删边操作并实时查询中心，可用 Link-Cut Tree 维护树的直径端点，每次操作后重新计算中心。
- 最小高度树：在图中（而非树中）找到使得到所有节点最大距离最小的节点集，称为最小高度树。对于一般图，中心可能不止两个，且需用Floyd-Warshall或多次BFS求解。
换根动态规划是解决”以每个节点为根时的子树信息”类问题的通用技巧。其核心思想是：先通过一次DFS计算子树内的信息（down），再通过一次DFS利用父节点的信息推导子树外的信息（up）。掌握这套”先下后上”的思维范式，将帮助你轻松应对树形DP中的绝大多数难题。
