# 1245. Tree Diameter
###### tags: `Leetcode` `FaceBook` `Medium` `DFS` `Graph`
Link: https://leetcode.com/problems/tree-diameter/
## 思路 $O(N)$ $O(N)$
先建图，然后随便挑一个点开始dfs遍历(因为只会有一个tree，而且是无向图，所以通过一个点，就可以找到所有的点)
如果有多个tree，或者是有向图，就需要多用一个map去存每个点和它下面的maxlen的对应
## Code

class Solution {
    int maxLen;
    public int treeDiameter(int[][] edges) {
        maxLen = 0;
        Map<Integer, List<Integer>> graph = new HashMap<>();
        for(int[] edge:edges){
            int u = edge[0];
            int v = edge[1];
            if(!graph.containsKey(u)){
                graph.put(u, new ArrayList<>());
            }
            graph.get(u).add(v);
        }
        dfs(0,-1,graph);
        return maxLen;
    }
    private int dfs(int u, int parent, Map<Integer, List<Integer>> graph){
        int[] length = new int[2];
        for(int v: graph.getOrDefault(u, new ArrayList<Integer>())){
            if(v == parent) continue;
            int currLen = dfs(v, u, graph)+1;
            if(currLen>=length[0]){
                length[1] = length[0];
                length[0] = currLen;
            }
            else if(currLen<length[0] && currLen>length[1]){
                length[1] = currLen;
            }
        }
        maxLen = Math.max(maxLen, length[0]+length[1]);
        return length[0];
    }
}