Simple O(n) solution


  • 0

    Keep track of the number of edges left for a vertex. In each round, mark vertices with edge count 1 as removed. Reduce the edge count on each neighbor of the removed vertex. Loop until the total number of edges is less than or equal to one.

    The reasoning is that we are collapsing vertices that have no other children to its root. If there are only two vertices, one vertex cant be collapsed into another. This explains the terminal condition for the rounds of deletion.

    public class Solution { 
        public IList<int> FindMinHeightTrees(int n, int[,] edges) {
        int[] graphVertices = new int[n];
        Dictionary<int, List<int>> graph = new Dictionary<int, List<int>>();
        for (int i = 0; i < n; i++)
        {
            graph[i] = new List<int>();
        }
    
        int edgeCount = 0;
        int rows = edges.GetLength(0);
        
        for (int i = 0; i < rows; i++)
        {
            edgeCount++;
            graphVertices[edges[i, 0]]++;
            graphVertices[edges[i, 1]]++;
            graph[edges[i, 0]].Add(edges[i,1]);
            graph[edges[i, 1]].Add(edges[i,0]);
        }
    
        bool[] removed = new bool[n];
        while(edgeCount >= 2)
        {
            List<int> remove = new List<int>();
            for(int i = 0; i < n; i++)
            {
                if (graphVertices[i] == 1)
                {
                    edgeCount--;
                    remove.Add(i);
                }
            }
    
            foreach(var r in remove)
            {
                graphVertices[r] = 0;
                removed[r] = true;
                foreach(var rn in graph[r])
                {
                    if (graphVertices[rn] > 0)
                    {
                        graphVertices[rn]--;
                    }
                }
            }
        }
    
        List<int> result = new List<int>();
        for (int i = 0; i < n; i++)
        {
            if (removed[i] == false)
            {
                result.Add(i);
            }
        }
    
        return result;
    }
    

    }


Log in to reply
 

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