Why there are at most two nodes left in the end?


  • 0
    F

    I'm a little confused about the result at first.
    The question is: How many MHTs can a graph have at most?
    Here is my thought: a graph can have one or two MHTs. This problem is similar to the median problem. An array may have one or two medians. If the nodes of the graph is greater than 2, we can always remove the leaves and the related edges to reduce the number of nodes down to 1 or 2. Beware that the graph has n vertices and n-1 edges and has no cycles.
    The solution is so straightforward:

    • remove leaves and the related edges
    • repeat until there are 1 or 2 vertices left
    • the left leaves are the results
    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
            if (n == 1) {
                return Collections.singletonList(0);
            }
            ArrayList<HashSet<Integer>> graph = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                graph.add(new HashSet<>());
            }
            for (int[] edge : edges) {
                graph.get(edge[0]).add(edge[1]);
                graph.get(edge[1]).add(edge[0]);
            }
            List<Integer> result = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                if (graph.get(i).size() == 1) {
                    result.add(i);
                }
            }
            while (n > 2) {
                n -= result.size();
                List<Integer> leaves = new ArrayList<>();
                for (Integer dst : result) {
                    int src = graph.get(dst).iterator().next();
                    graph.get(src).remove(dst);
                    if (graph.get(src).size() == 1) {
                        leaves.add(src);
                    }
                }
                result = leaves;
            }
            return result;
        }

Log in to reply
 

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