Removing leaf approach with slight improvement, 22ms beats 99%


  • 0
    I
    public class Solution {
        //22ms, beats 99%
        public List<Integer> findMinHeightTrees(int n, int[][] edges) {
            if(n == 1) return Collections.singletonList(0);
            
            final List<Integer>[] array = new List[n];
            for(int i=0; i<n; i++) {
                array[i] = new ArrayList<Integer>();
            }
            
            final int[] outlink = new int[n];
            
            for(int[] edge : edges) {
                array[edge[0]].add(edge[1]);
                outlink[edge[0]]++;
                
                array[edge[1]].add(edge[0]);
                outlink[edge[1]]++;
            }
            
            List<Integer> leaves = new ArrayList<>();
            
            for(int i=0; i<n; i++) {
                // i -> only 1 vertex, so we can take vertex i out in next round
                if(outlink[i] == 1) leaves.add(i);
            }
            
            while(n > leaves.size()) {
                n -= leaves.size();
                
                final List<Integer> newLeaves = new ArrayList<>();
                
                for(final int i : leaves) {
                    for(final int j : array[i]) {
                        outlink[j]--;
                        if(outlink[j] == 1) newLeaves.add(j);
                    }
                }
    
                leaves = newLeaves;
            }
            
            return leaves;
        }
    }
    

Log in to reply
 

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