My basic BFS idea solution is right but time exceed


  • 0
    G
    class node{
        int val;
        int level;
        node(int val, int level){
            this.val = val;
            this.level = level;
        }
    }
    
    
    public class Solution {
        public List<Integer> findMinHeightTrees(int n, int[][] edges) {
            List<Integer> res = new ArrayList<Integer>();
            if(edges.length==0){
                for(int i=0;i<n;i++){
                    res.add(i);
                }
                return res;
            }
            
            HashMap<Integer,Integer> map = new HashMap<>();
            int mindeep = Integer.MAX_VALUE;
            for(int i=0;i<n;i++){
                for(int[]arr:edges){
                    if(arr[0]==i){
                        int height = bfs(edges,i);
                        if(height<mindeep){
                            mindeep = height;
                        }
                        map.put(i,height);
                        break;
                    }
                    else if(arr[1]==i){
                        int height = bfs(edges,i);
                        if(height<mindeep){
                            mindeep = height;
                        }
                        map.put(i,height);
                        break;
                    }
                }
            }
            
           
            for(int key:map.keySet()){
                if(map.get(key)==mindeep){
                    res.add(key);
                }
            }
            
            return res;
        }
        
        public int bfs(int[][] edges, int i){
            int maxdeep = 0;
            HashSet<Integer> set = new HashSet<>();
            Queue<node> qq = new LinkedList<node>();
            qq.add(new node(i,0));
            while(!qq.isEmpty()){
                node temp = qq.poll();
                if(temp.level>maxdeep){
                    maxdeep = temp.level;
                }
                int val = temp.val;
                set.add(val);
                for(int[]arr:edges){
                    if(arr[0]==val && !set.contains(arr[1])){
                        qq.add(new node(arr[1],temp.level+1));
                    }
                    if(arr[1]==val && !set.contains(arr[0])){
                        qq.add(new node(arr[0],temp.level+1));
                    }
                }
                
            }
            
            return maxdeep;
        }
    }

Log in to reply
 

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