310. Minimum Height Trees - cocoder39/coco39_LC GitHub Wiki

310. Minimum Height Trees

class Solution:
    def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:
        graph = collections.defaultdict(set)
        for node1, node2 in edges:
            graph[node1].add(node2)
            graph[node2].add(node1)
        
        if len(graph) <= 2:
            return [i for i in range(n)]
                
        leaves = []
        for node, neighbors in graph.items():
            if len(neighbors) == 1:
                leaves.append(node)
        
        while len(graph) > 2:
            # remove leaves layer by layer
            new_leaves = []
            for leaf in leaves:
                # leaf has single neighbor
                neighbor = graph[leaf].pop()
                del graph[leaf]
                graph[neighbor].remove(leaf)
                if len(graph[neighbor]) == 1:
                    # the degree of neighbor might be reduced to 0 
                    # that's fine as long we capture it when its degree is 1
                    new_leaves.append(neighbor)
            leaves = new_leaves
    
        return leaves

cite from here

Some statements for tree in graph theory:

  • A tree is an undirected graph in which any two vertices are connected by exactly one path.
  • Any connected graph who has n nodes with n-1 edges is a tree.
  • The degree of a vertex of a graph is the number of edges incident to the vertex.
  • A leaf is a vertex of degree 1. An internal vertex is a vertex of degree at least 2.
  • A path graph is a tree with two or more vertices that is not branched at all.
  • A tree is called a rooted tree if one vertex has been designated the root.
  • The height of a rooted tree is the number of edges on the longest downward path between root and a leaf.

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 (even edges) or they are one step away (odd edges), (depends on the parity of n), we have the roots we want.

T = O(n), S = O(n)

vector<int> findMinHeightTrees(int n, vector<pair<int, int>>& edges) {
        if (edges.empty())
            return {0};
        
        unordered_map<int, unordered_set<int>> adj;
        for (auto edge : edges) { 
            adj[edge.first].insert(edge.second);
            adj[edge.second].insert(edge.first);
        }
        
        queue<int> leave;
        for (auto i : adj) {
            if (i.second.size() == 1) //leave node
                leave.push(i.first);
        }
        
        while (n > 2) {
            int sz = leave.size();
            n -= sz;
            while (sz > 0) {
                int v1 = leave.front();
                leave.pop();
                sz--;
                
                int v2 = *(adj[v1].begin());
                adj[v2].erase(v1);
                if (adj[v2].size() == 1)
                    leave.push(v2);
            }
        }
        
        vector<int> res;
        while (! leave.empty()) {
            res.push_back(leave.front());
            leave.pop();
        }
        return res;
    }
⚠️ **GitHub.com Fallback** ⚠️