题解 | #多叉树的直径#

import java.util.*;

/*
 * public class Interval {
 *   int start;
 *   int end;
 * }
 */

public class Solution {
    private List<List<Edge>> graph;
    private int maxDistance = 0; // 本次dfs最远距离
    private int maxIndex = -1; // 本次dfs最远节点

    /**
     * 树的直径
     *
     * @param n          int整型 树的节点个数
     * @param Tree_edge  Interval类一维数组 树的边
     * @param Edge_value int整型一维数组 边的权值
     * @return int整型
     */
    public int solve(int n, Interval[] Tree_edge, int[] Edge_value) {
        // 以邻接表的方式建立图
        this.graph = new ArrayList<>(n);
        // 初始化
        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }
        for (int i = 0; i < Tree_edge.length; i++) {
            // 由于是无向图，每条边都是双向的
            graph.get(Tree_edge[i].start).add(new Edge(Tree_edge[i].end, Edge_value[i]));
            graph.get(Tree_edge[i].end).add(new Edge(Tree_edge[i].start, Edge_value[i]));
        }
        dfs(0, -1, 0);
        maxDistance = 0;
        dfs(far, -1, 0);
        return maxDistance;
    }

    private void dfs(int cur, int parent, int distance) {
        if (distance > maxDistance) {
            maxDistance = distance;
            maxIndex = cur;
        }
        List<Edge> edges = graph.get(cur);
        for (Edge edge : edges) {
            int end = edge.end;
            if (end == parent) { // 不能往回走到父节点
                continue;
            }
            dfs(end, cur, distance + edge.weight);
        }
    }

    // 邻接表的边结构
    private class Edge {
        int end; // 边的终点
        int weight; // 权重

        public Edge(int end, int weight) {
            this.end = end;
            this.weight = weight;
        }
    }
}

import java.util.*;

/*
 * public class Interval {
 *   int start;
 *   int end;
 * }
 */

public class Solution {
    private List<List<Edge>> graph;
    private int maxDistance = 0; // 本次dfs最远距离
    private int maxIndex = -1; // 本次dfs最远节点

    /**
     * 树的直径
     *
     * @param n          int整型 树的节点个数
     * @param Tree_edge  Interval类一维数组 树的边
     * @param Edge_value int整型一维数组 边的权值
     * @return int整型
     */
    public int solve(int n, Interval[] Tree_edge, int[] Edge_value) {
        // 以邻接表的方式建立图
        this.graph = new ArrayList<>(n);
        // 初始化
        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }
        for (int i = 0; i < Tree_edge.length; i++) {
            // 由于是无向图，每条边都是双向的
            graph.get(Tree_edge[i].start).add(new Edge(Tree_edge[i].end, Edge_value[i]));
            graph.get(Tree_edge[i].end).add(new Edge(Tree_edge[i].start, Edge_value[i]));
        }
        bfs(0); // 从节点0开始
        maxDistance = 0;
        bfs(maxIndex); // 
        return maxDistance;
    }

    private void bfs(int start) {
        Queue<Node> queue = new LinkedList<>();
        queue.offer(new Node(start, -1, 0));
        while(!queue.isEmpty()) {
            // 取出当前节点
            Node node = queue.poll();
            int cur = node.cur;
            int parent = node.parent;
            int distance = node.distance;
            // 如果大于maxDistance，则进行更新
            if (distance > maxDistance) {
                maxDistance = distance;
                maxIndex = cur;
            }
            List<Edge> edges = graph.get(cur);
            for (Edge edge : edges) {
                if (edge.end == parent) {
                    continue;
                }
                queue.offer(new Node(edge.end, cur, distance + edge.weight));
            }
        }
    }

    // 邻接表的边结构
    private class Edge {
        public int end; // 边的终点
        public int weight; // 权重

        public Edge(int end, int weight) {
            this.end = end;
            this.weight = weight;
        }
    }
    
    // 保存遍历到当前节点时的各种信息
    private class Node {
        public int cur; // 当前节点
        public int parent; // 父节点
        public int distance; // 初始节点到当前节点的距离

        public Node(int cur, int parent, int distance) {
            this.cur = cur;
            this.parent = parent;
            this.distance = distance;
        }
    }
}