树的直径

表面说是树，实际上是无向图的遍历。
树的直径就是两个节点之间最远的距离，而距离跟边权值有关。
所以要进行两次遍历，并在每次遍历记录比较出最大的边权值和

• 找到从根节点开始的最远的节点
• 从这个最远的节点出发找到最远的令一个节点

import java.util.*;

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

public class Solution {
    /**
     * 树的直径
     * @param n int整型 树的节点个数
     * @param Tree_edge Interval类一维数组 树的边
     * @param Edge_value int整型一维数组 边的权值
     * @return int整型
     */
    List<List<Integer>> graph = new ArrayList<>();    //用来存图结构
    Map<Integer, Map<Integer,Integer>> table =new  HashMap<>(); //用来存图权重

    int maxEdges=0;
    int maxIndex=-1;

    public int solve (int n, Interval[] Tree_edge, int[] Edge_value) {
        // write code here
        for(int i=0; i<n; i++){
            graph.add( new ArrayList<Integer>());
        }

        //构建graph，和table用于查询各边的权重
        for(int i=0; i<Tree_edge.length;i++){
            Interval edge=Tree_edge[i];
            graph.get(edge.start).add(edge.end); //建立图
            graph.get(edge.end).add(edge.start); //因为是无向图，所以也得反向连接一下

            //构建表
            if(!table.containsKey(edge.start)) table.put(edge.start, new HashMap<Integer, Integer>());
            table.get(edge.start).put(edge.end,Edge_value[i]);
            if(!table.containsKey(edge.end)) table.put(edge.end, new HashMap<Integer, Integer>()); 
            table.get(edge.end).put(edge.start,Edge_value[i]);

         }
        //找到从根节点开始遍历到的最大边权值和的节点
        dfs(0,0,-1);
        //再从这个节点找到最大边权值和的节点
        dfs(0,maxIndex,-1);
        //返回最大边权值和
        return maxEdges;

    }

    public void dfs(int count, int node, int parent){
        List<Integer> cur = graph.get(node);

        for(int i=0; i<cur.size(); i++){     //可行性剪枝？反正就是不允许dfs往回走到父节点
            if(cur.get(i)==parent){
                continue; 
            }
            int value=table.get(node).get(cur.get(i));
            //每一轮都加上边权值，遍历到最深的时候， count就是边权值和了
            dfs(count+value, cur.get(i),node);
        }
         //每个边权值和进行比较
        if(count>maxEdges){
            //用maxEdges记录最大的边权值和
            maxEdges=count;
            //用maxIndex记录到达的最深的节点
            maxIndex=node;
        }
    }
}