题目
题目链接：https://www.lintcode.com/problem/3686/
思路
1.利用map创建图
2.找到直径的其中一个端点last,通过bfs可以实现
3.从last出发，再次bfs,有多少层，直径就是多少
Java代码
/*** Definition for Undirected graph.* class UndirectedGraphNode {* int label;* List<UndirectedGraphNode> neighbors;* UndirectedGraphNode(int x) {* label = x;* neighbors = new ArrayList<UndirectedGraphNode>();* }* }*/public class Solution {/*** @param root: the root of the tree* @return: Maximum diameter of the N-ary Tree*/public int diameter(UndirectedGraphNode root) {if(root ==null) return 0;Map<UndirectedGraphNode, Set<UndirectedGraphNode>> graph = new HashMap<>();buildGraph(root, graph);//宽度右边遍历2次，第一次最后遍历到的节点last,// last一定是直径的一个端点之一// 那么从last出发，再次宽度优先遍历，有几层，直径就是几Set<UndirectedGraphNode> visited = new HashSet<>();UndirectedGraphNode last = null;Queue<UndirectedGraphNode> q = new LinkedList<>();q.add(root);visited.add(root);while (!q.isEmpty()){int size = q.size();for (int i = 0; i <size ; i++) {UndirectedGraphNode pop = q.poll();Set<UndirectedGraphNode> nexts = graph.get(pop);for (UndirectedGraphNode next : nexts) {if(!visited.contains(next)){q.add(next);last = next;visited.add(next);}}}}//从last出发再次BFSint ans =0;visited.clear();q.add(last);visited.add(last);while (!q.isEmpty()){ans++;int size = q.size();for (int i = 0; i <size ; i++) {UndirectedGraphNode pop = q.poll();Set<UndirectedGraphNode> nexts = graph.get(pop);for (UndirectedGraphNode next : nexts) {if(!visited.contains(next)){q.add(next);visited.add(next);}}}}return ans-1;}public void buildGraph(UndirectedGraphNode cur, Map<UndirectedGraphNode, Set<UndirectedGraphNode>> g) {//建立图if (cur == null) return;if (!g.containsKey(cur)) {g.put(cur, new HashSet<>());}for (UndirectedGraphNode next : cur.neighbors) {if (!g.containsKey(next)) {g.put(next, new HashSet<>());}g.get(cur).add(next);g.get(next).add(cur);buildGraph(next, g);}}
}
)
