题解 | #多叉树的直径,时间O(n) , 空间(mn)#

import java.util.*;

/*
 * public class Interval {
 *   int start;
 *   int end;
 * }
 */
class Edge {
    int start ;
    int end ;
    int weight ;
    Edge(int start , int end , int weight) {
        this.start = start ;
        this.end = end ;
        this.weight = weight ;
    }
}
class Node {
    int val ;
    Set<Edge> edges ;
    Node(int val) {
        this.val = val ;
        edges = new HashSet<>() ;
    }
}
class Graph {
    Map<Integer , Node> nodesMap ;
    Set<Edge> edges ;
    Graph() {
        this.nodesMap = new HashMap<>() ;
        this.edges = new HashSet<>() ;
    }
}
public class Solution {
    /**
     * 树的直径
     * @param n int整型 树的节点个数
     * @param Tree_edge Interval类一维数组 树的边
     * @param Edge_value int整型一维数组 边的权值
     * @return int整型
     */
    public int solve (int n, Interval[] Tree_edge, int[] Edge_value) {
        //建图
        Graph graph = new Graph() ;
        for(int i = 0 ; i < n ; i ++) {
            graph.nodesMap.put(i , new Node(i)) ;
        }
        for(int j = 0 ; j < Tree_edge.length ; j ++) {
            int start = Tree_edge[j].start ;
            int end = Tree_edge[j].end ;
            int weight = Edge_value[j] ;
            Edge new_edge1 = new Edge(start , end , weight) ;
            Edge new_edge2 = new Edge(end , start , weight) ;
            graph.edges.add(new_edge1) ;
            graph.edges.add(new_edge2) ;
            graph.nodesMap.get(start).edges.add(new_edge1) ;
            graph.nodesMap.get(end).edges.add(new_edge2) ;
        }
        //第一次dfs，找到直径的一个端点
        Node startNode = graph.nodesMap.get(0) ;
        Node[] res = new Node[]{startNode} ;
        int[] maxLen = {0} ;
        int nodeSize = graph.nodesMap.size() ;
        dfs_findMax(graph , startNode , res , new boolean[nodeSize] , 0 , maxLen) ;
        startNode = res[0] ;
        maxLen[0] = 0 ;
        dfs_findMax(graph , startNode , res , new boolean[nodeSize] , 0 , maxLen) ;
        return maxLen[0] ;
    }
    public void dfs_findMax( Graph graph, Node node , Node[] res , boolean[] isVisited , int len , int[] maxLen) {
        if(isVisited[node.val]) return ;
        isVisited[node.val] = true ;
        Set<Edge> edges = node.edges ;
        for(Edge e : edges) {
            if(isVisited[e.end]) continue ; 
            Node end = graph.nodesMap.get(e.end) ;
            len += e.weight ;
            if(len > maxLen[0]) {
                maxLen[0] = len ;
                res[0] = end ;
            }
            dfs_findMax(graph , end , res , isVisited , len , maxLen) ;
            len -= e.weight ;
        }
    }
}