Java bfs-like AC solution using user defined graph Node class


  • 1
    public class Solution {
        public List<Integer> findMinHeightTrees(int n, int[][] edges) {
            Map<Integer, Node> graph = new HashMap<>();
            for (int i = 0; i < n; i++) {
                graph.put(i, new Node(i));
            }
            
            for (int[] edge : edges) {
                graph.get(edge[0]).neighbors.add(graph.get(edge[1]));
                graph.get(edge[1]).neighbors.add(graph.get(edge[0]));
                graph.get(edge[0]).degree++;
                graph.get(edge[1]).degree++;
            }
            
            Queue<Node> queue = new LinkedList<>();
            for (int index : graph.keySet()) {
                if (graph.get(index).degree == 1) {
                    queue.offer(graph.get(index));
                }
            }
            
            while (n > 2) {
                int size = queue.size();
                for (int i = 0; i < size; i++) {
                    Node leaf = queue.poll();
                    Node neighbor = leaf.neighbors.iterator().next();
                    neighbor.neighbors.remove(leaf);//remove leaf from its neighbor's adj list
                    graph.remove(leaf.label);//remove leaf self
                    n--;
                    if (--neighbor.degree == 1) {
                        queue.offer(neighbor);
                    }
                }
            }
            
            return new ArrayList<>(graph.keySet());
            
        }
    }
    
    class Node {
        int label;
        int degree;
        Set<Node> neighbors;
        public Node(int index) {
            label = index;
            neighbors = new HashSet<>();
        }
    }

  • 0
    M

    Inside the bfs-process, when deleting the leaf in its neighbor's adjacent nodes' list, you can just check whether the neighbor's new degree is 1 or not. Instead of looping through the leaf neighbor to find the nodes with degree 1,


  • 0

    thanks for reminding me! I have modified that.


Log in to reply
 

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