Simple BFS solution


  • -1
    V
    public boolean validTree(int n, int[][] edges) {
        HashMap<Integer, List<Integer>> map = new HashMap<>();
        HashSet<Integer> set = new HashSet<>();
        for(int[] edge : edges){
            if(map.containsKey(edge[0])) map.get(edge[0]).add(edge[1]);
            else{
                List<Integer> l = new ArrayList<>();
                l.add(edge[1]);
                map.put(edge[0], l);
            }
            if(map.containsKey(edge[1])) map.get(edge[1]).add(edge[0]);
            else{
                List<Integer> l = new ArrayList<>();
                l.add(edge[0]);
                map.put(edge[1], l);
            }
        }
        System.out.println(map);
        Queue<Integer> queue = new LinkedList<>();
        queue.add(-1);queue.add(0);
        while(!queue.isEmpty()){
            int size = queue.size() / 2;
            for(int i = 0; i < size; i++){
                int predecessor = queue.remove();
                int node = queue.remove();
                set.add(node);
                if(map.containsKey(node)){
                    List<Integer> neighbours = map.get(node);
                    for(Integer neighbour : neighbours){
                        if(neighbour == predecessor) continue;
                        if(set.contains(neighbour)) return false;
                        queue.add(node); queue.add(neighbour);
                    }
                }
            }
        }
        return set.size() == n;
    }

  • 0
    V

    why is this down voted? :)


Log in to reply
 

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