一些树上问题：
树的直径：
import java.util.*;public class TreeDiameter {static List<List<Integer>> tree; // 用邻接表存储树结构static int[] depth; // 记录每个节点的深度public static void main(String[] args) {Scanner sc = new Scanner(System.in);// 1. 读取输入System.out.println("请输入节点数量：");int n = sc.nextInt();// 2. 初始化树tree = new ArrayList<>();for (int i = 0; i < n; i++) {tree.add(new ArrayList<>());}depth = new int[n];System.out.println("请输入" + (n-1) + "条边：");for (int i = 0; i < n-1; i++) {int u = sc.nextInt();int v = sc.nextInt();tree.get(u).add(v);tree.get(v).add(u);}// 3. 计算直径// 第一次BFS：从节点0出发，找到最远点uint u = bfs(0);// 第二次BFS：从u出发，找到最远点vint v = bfs(u);// 直径就是u和v之间的距离System.out.println("树的直径长度（边数）：" + depth[v]);}// BFS方法：返回离起点最远的节点static int bfs(int start) {Arrays.fill(depth, -1); // 初始化所有深度为-1Queue<Integer> queue = new LinkedList<>();queue.add(start);depth[start] = 0;int farthest = start; // 记录最远节点while (!queue.isEmpty()) {int current = queue.poll();// 遍历所有邻居for (int neighbor : tree.get(current)) {if (depth[neighbor] == -1) { // 如果邻居未被访问depth[neighbor] = depth[current] + 1;queue.add(neighbor);// 更新最远节点if (depth[neighbor] > depth[farthest]) {farthest = neighbor;}}}}return farthest;}
}树的重心
import java.util.*;public class TreeCentroid {static List<List<Integer>> tree; // 树的邻接表表示static int[] size; // 存储每个节点的子树大小static int centroid; // 重心static int minMaxSubtree; // 最小化后的最大子树大小public static void main(String[] args) {Scanner sc = new Scanner(System.in);// 1. 读取输入并构建树System.out.println("请输入节点数量：");int n = sc.nextInt();initializeTree(n);System.out.println("请输入" + (n-1) + "条边：");for (int i = 0; i < n-1; i++) {int u = sc.nextInt();int v = sc.nextInt();addEdge(u, v);}// 2. 计算重心findCentroid(n);System.out.println("树的重心是：" + centroid);}static void initializeTree(int n) {tree = new ArrayList<>();size = new int[n];for (int i = 0; i < n; i++) {tree.add(new ArrayList<>());}minMaxSubtree = Integer.MAX_VALUE;}static void addEdge(int u, int v) {tree.get(u).add(v);tree.get(v).add(u);}static void findCentroid(int totalNodes) {dfs(0, -1, totalNodes);}static void dfs(int node, int parent, int totalNodes) {size[node] = 1; // 当前节点自身int maxSubtree = 0; // 存储当前节点的最大子树大小// 遍历所有子节点for (int child : tree.get(node)) {if (child != parent) { // 避免回溯到父节点dfs(child, node, totalNodes);size[node] += size[child]; // 累加子树大小maxSubtree = Math.max(maxSubtree, size[child]); // 更新最大子树}}// 检查父节点方向的"子树"（总节点数 - 当前子树大小）maxSubtree = Math.max(maxSubtree, totalNodes - size[node]);// 更新重心if (maxSubtree < minMaxSubtree) {minMaxSubtree = maxSubtree;centroid = node;}}
}