Java Solution beats 99% using DFS


  • -2
    H
    public class Solution {
        public static class Node{
            int num;
            int val;
            List<Integer> adj;
            public Node(int num){
                this.num = num;
                this.adj = new ArrayList<Integer>();
            }
        }
        public List<Integer> findMinHeightTrees(int n, int[][] edges) {
            Node[] graph = new Node[n];
            for (int i = 0; i < n; i++)
                graph[i] = new Node(i);
            // build graph
            for (int i = 0; i < edges.length; i++) {
                int a = edges[i][0];
                int b = edges[i][1];
                graph[a].adj.add(b);
                graph[b].adj.add(a);
            }
            boolean[] visited = new boolean[n];
            DFS(graph, 0, 0, visited);
            Arrays.fill(visited, false);
            graph[farest].val = 0;
            DFS(graph, farest, 0, visited);
            int length = graph[farest].val;
            // find the mid
            int mid = length / 2;
            boolean two = true;
            if (length % 2 == 0) {
                two = false;
            } else {
                mid = mid + 1;
            }
            List<Integer> ans = new ArrayList<Integer>();
            Node cur = graph[farest];
            while (cur.val != mid) {
                for (int i : cur.adj) {
                    if (graph[i].val + 1 == cur.val) {
                        cur = graph[i];
                        break;
                    }
                }
            }
            ans.add(cur.num);
            if (two) {
                for (int i : cur.adj) {
                    if (graph[i].val + 1 == cur.val) {
                        cur = graph[i];
                        break;
                    }
                }
                ans.add(cur.num);
            }
            return ans;
            
        }
        private int farest = 0;
        private void DFS(Node[] graph, int start, int layer, boolean[] visited){
            visited[start] = true;
            graph[start].val = layer;
            if(graph[farest].val < graph[start].val) farest = start;
            List<Integer> adj = graph[start].adj;
            for(int i:adj){
                if(!visited[i])
                    DFS(graph, i, layer+1, visited);    
            }
        }
    }

  • 0
    U

    long and uncommented.....


  • 0
    H

    you can figure it out yourself.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.