题解 | #多叉树的直径#

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整型
     */
    class node{
        int num;
        int weight;
        public node(int num,int weight){
            this.num=num;
            this.weight=weight;
        }
    }
    Map<Integer,List<node>> map=new HashMap();
    boolean []used;
    public int solve (int n, Interval[] Tree_edge, int[] Edge_value) {
        used=new boolean[n];
        //初始化无向图
        for(int i=0;i<Tree_edge.length;i++){
            if(map.containsKey(Tree_edge[i].start)){
                map.get(Tree_edge[i].start).add(new node(Tree_edge[i].end,Edge_value[i]));
            }
            else{
                map.put(Tree_edge[i].start,new ArrayList<node>());
                map.get(Tree_edge[i].start).add(new node(Tree_edge[i].end,Edge_value[i]));
            }
            if(map.containsKey(Tree_edge[i].end)){
                map.get(Tree_edge[i].end).add(new node(Tree_edge[i].start,Edge_value[i]));
            }
            else{
                map.put(Tree_edge[i].end,new ArrayList<node>());
                map.get(Tree_edge[i].end).add(new node(Tree_edge[i].start,Edge_value[i]));
            }
        }
         node endPoint1=new node(0,0);
         node endPoint2=new node(0,0);
        //寻找第一个端点
        used[0]=true;
        dfs(0,0,used,endPoint1);
        for(int i=0;i<used.length;i++){
            used[i]=false;
        }
        used[endPoint1.num]=true;
        dfs(endPoint1.num,0,used,endPoint2);
        return endPoint2.weight;
        
    }
    public void dfs(int startPoint,int lastLength,boolean []used,node endP){
        List<node> neighbor=map.get(startPoint);
        int maxTmp=0;
        int j=0;
        for(j=0;j<neighbor.size();j++){
           if(used[neighbor.get(j).num]==false){
               break;
           }  
        }
        if(j==neighbor.size()){
            if(lastLength>endP.weight){
                endP.weight=lastLength;
                endP.num=startPoint;
            }
            return;
        }
        for(int i=0;i<neighbor.size();i++){
            if(used[neighbor.get(i).num]==false){
                used[neighbor.get(i).num]=true;
                dfs(neighbor.get(i).num,lastLength+neighbor.get(i).weight,used,endP);
                used[neighbor.get(i).num]=false;
            }
        }
        
    }
//     public int bfs(int node){
//         Set<Integer> set=new HashSet();
//         Queue<int[]> q=new LinkedList<>();
//         int maxLen=0;
//         q.add(new int[]{node,0});
//         set.add(node);
//         bigSet.add(node);
//         while(!q.isEmpty()){
//             int size=q.size();
//             for(int i=0;i<size;i++){
//                 int[] key=q.poll();
//                 HashMap<Integer,Integer> hash=map.get(key[0]);
//                 for(int round:hash.keySet()){
//                     int nextPoint=round;
//                     int nextLength=hash.get(round)+key[1];//保存的距离
//                 if(!set.contains(nextPoint)){
//                     q.add(new int[]{nextPoint,nextLength});
//                     set.add(nextPoint);
//                     maxLen=Math.max(maxLen,nextLength);
//                 }
                    
//                 }
//             }
            
//         }
//         return maxLen;
//     }
    
    
    
}