Share some thoughts


  • 422

    See here for a better view

    First let's review some statement for tree in graph theory:

    (1) A tree is an undirected graph in which any two vertices are
    connected by exactly one path.

    (2) Any connected graph who has n nodes with n-1 edges is a tree.

    (3) The degree of a vertex of a graph is the number of
    edges incident to the vertex.

    (4) A leaf is a vertex of degree 1. An internal vertex is a vertex of
    degree at least 2.

    (5) A path graph is a tree with two or more vertices that is not
    branched at all.

    (6) A tree is called a rooted tree if one vertex has been designated
    the root.

    (7) The height of a rooted tree is the number of edges on the longest
    downward path between root and a leaf.

    OK. Let's stop here and look at our problem.

    Our problem want us to find the minimum height trees and return their root labels. First we can think about a simple case -- a path graph.

    For a path graph of n nodes, find the minimum height trees is trivial. Just designate the middle point(s) as roots.

    Despite its triviality, let design a algorithm to find them.

    Suppose we don't know n, nor do we have random access of the nodes. We have to traversal. It is very easy to get the idea of two pointers. One from each end and move at the same speed. When they meet or they are one step away, (depends on the parity of n), we have the roots we want.

    This gives us a lot of useful ideas to crack our real problem.

    For a tree we can do some thing similar. We start from every end, by end we mean vertex of degree 1 (aka leaves). We let the pointers move the same speed. When two pointers meet, we keep only one of them, until the last two pointers meet or one step away we then find the roots.

    It is easy to see that the last two pointers are from the two ends of the longest path in the graph.

    The actual implementation is similar to the BFS topological sort. Remove the leaves, update the degrees of inner vertexes. Then remove the new leaves. Doing so level by level until there are 2 or 1 nodes left. What's left is our answer!

    The time complexity and space complexity are both O(n).

    Note that for a tree we always have V = n, E = n-1.

    Java

    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        if (n == 1) return Collections.singletonList(0);
    
        List<Set<Integer>> adj = new ArrayList<>(n);
        for (int i = 0; i < n; ++i) adj.add(new HashSet<>());
        for (int[] edge : edges) {
            adj.get(edge[0]).add(edge[1]);
            adj.get(edge[1]).add(edge[0]);
        }
    
        List<Integer> leaves = new ArrayList<>();
        for (int i = 0; i < n; ++i)
            if (adj.get(i).size() == 1) leaves.add(i);
    
        while (n > 2) {
            n -= leaves.size();
            List<Integer> newLeaves = new ArrayList<>();
            for (int i : leaves) {
                int j = adj.get(i).iterator().next();
                adj.get(j).remove(i);
                if (adj.get(j).size() == 1) newLeaves.add(j);
            }
            leaves = newLeaves;
        }
        return leaves;
    }
    
    // Runtime: 53 ms
    

    Python

    def findMinHeightTrees(self, n, edges):
        if n == 1: return [0] 
        adj = [set() for _ in xrange(n)]
        for i, j in edges:
            adj[i].add(j)
            adj[j].add(i)
    
        leaves = [i for i in xrange(n) if len(adj[i]) == 1]
    
        while n > 2:
            n -= len(leaves)
            newLeaves = []
            for i in leaves:
                j = adj[i].pop()
                adj[j].remove(i)
                if len(adj[j]) == 1: newLeaves.append(j)
            leaves = newLeaves
        return leaves
    	
    # Runtime : 104ms

  • 0
    T

    Worth noting that the int j : adj.get(i) loop will only run for a single j value, because i is a leaf, and hence it has only a single edge toward the rest of the graph. It's a dirty trick to skip thorugh nodes with 0 edges.

    The if <=1 add logic which fills the leaves the first time contradicts your statements above:

    A leaf is a vertex of degree 1.
    We start from every end, by end we mean vertex of degree 1 (aka leaves).

    It may be better to add an exception right at the top for that single case when this (the equals in <=) matters.


  • 0

    You are correct. seems we can change that for loop into a peek.

    And that if <= 1 logic is only used for the case with n = 1. For n > 1, there won't be a node with 0 degree before we remove leaves.

    I was just lazy and don't want to put a if (n==1) return Collections.singletonList(0); in front of the code.


  • 0
    T

    Well, the code is still valid, it's just misleading to use a for to access 0 or 1 elements (without a comment)... If you change the <= to == the rest of the code can assume that adj.get(leaf).iterator().next() always exists.


  • 0

    I see your point now.

    I didn't use for to avoid 0 degree node in leaves.

    The only 0 degree node will be n == 1 case. and that won't go into the while.

    I didn't use <= inside the loop. I used ==.

    So adj.get(leaf).iterator().next() always exists.

    But you are right, it is worthwhile to put the guard to make it clear and avoid <=


  • 0

    I made the change. Thank you!


  • 0

    Great job! Using List is faster than my solution using HashMap.


  • 0

    Whenever the Direct Access Table is possible I usually avoid Hash Table. It it better both in time and space.

    Too bad java do not support Generic Arrays like Set<Integer>[] Otherwise I would even avoid the List


  • 0

    Thanks! I agree. You actually can do this peisi (although it might be type unsafe):

    Set[] adj = new Set[n];
    for(int i = 0; i < n; ++i) adj.add(new HashSet<Integer>());

  • 0

    Yes. I know this trick. When use the elements you need to cast and it is not worth it.


  • 0

    Can we do this Set<Integer>[] adj = (Set<Integer>[])new HashSet[n]


  • 4
    S

    Why they are at most 2 MHT? Thank you!


  • 0

    Imagine you remove the leaves level by level. If there are more than 3 nodes left it can not be all leaves. You can find that out by definition of leaves and tree.


  • 0
    G

    Thank you for sharing these great thoughts!


  • -28
    K

    The problem with this method is you don't check if there is a loop in the map, or whether all nodes are connected. I suggest do one round of DFS or BFS to check the integrity of the nodes, and also add more test cases to the OJ.


  • 2

    Please. The problem is stated it is "a undirected graph with tree characteristics" which means all vertexes is connected. If it is an arbitrary graph i would agree.


  • 0
    T

    @peisi what's wrong with this compiling code?

    Set<String>[] sets = new Set[10];
    sets[2] = new HashSet<>(); // autogenerics
    sets[2].add("hello");
    //sets[2].add(3); // no suitable method found for add(int)
    String s = sets[2].iterator().next(); // no cast
    

    if you're bothered by the warning just do:

    @SuppressWarnings("unchecked") Set<String>[] sets = new Set[10];

  • 0

    This does work. But I will stick to List anyway.....


  • 0

    Great problem, I like the way you go through the idea! Thanks @peisi!


  • 0

    @TWiStErRob
    I have tested the implement with your code. For this problem it runs in 58ms for Set<Integer>[] and 54ms for List<Set<Integer>>.

    Therefore List seems better both ways.


Log in to reply
 

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