310. 最小高度树

  1. class Solution {
  2.     List<Integer> res = new ArrayList<Integer>();
  4.     public List<Integer> findMinHeightTrees(int n, int[][] edges) {
  5.         if (n == 1) {
  6.             res.add(0);
  7.             return res;
  8.         }
  9.         List<Integer>[] graph = new List[n];
  10.         for (int i = 0; i < n; ++i) graph[i] = new ArrayList<Integer>();
  11.         //创建图
  12.         for (int[] edge : edges) {
  13.             graph[edge[0]].add(edge[1]);
  14.             graph[edge[1]].add(edge[0]);
  15.         }
  17.         int[] parent = new int[n];
  18.         Arrays.fill(parent, -1);
  20.         int x = findLongestNode(graph, 0, parent);
  21.         int y = findLongestNode(graph, x, parent);
  23.         List<Integer> path = new ArrayList<Integer>();
  24.         parent[x] = -1;
  25.         while (y != -1) {
  26.             path.add(y);
  27.             y = parent[y];
  28.         }
  30.         if (path.size() % 2 == 0) {
  31.             res.add(path.get(path.size() / 2 - 1));
  32.             res.add(path.get(path.size() / 2));
  33.         } else {
  34.             res.add(path.get(path.size() / 2));
  35.         }
  36.         return res;
  37.     }
  39.     public int findLongestNode(List<Integer>[] graph, int start, int[] parent) {
  40.         int n = graph.length;
  41.         boolean[] visit = new boolean[n];
  42.         Queue<Integer> queue = new LinkedList<>();
  43.         visit[start] = true;
  44.         queue.offer(start);
  46.         int node = -1;
  47.         while(!queue.isEmpty()) {
  48.             node = queue.poll();
  49.             for (int i : graph[node]) {
  50.                 if (visit[i] == false) {
  51.                     visit[i] = true;
  52.                     parent[i] = node;
  53.                     queue.offer(i);
  54.                 }
  55.             }
  57.         }
  58.         return node;
  60.     }
  63. }