C# implementation


  • 0
    C

    C# implementation. Refer https://discuss.leetcode.com/topic/30572/share-some-thoughts about idea

            public IList<int> FindMinHeightTrees(int n, int[,] edges)
            {
                List<int> leaves = new List<int>();
                if (edges.Length == 0)
                {
                    leaves.Add(0); // Actually I'm no very clear why OJ test case asking this
                    return leaves;
                }
    
                Dictionary<int, List<int>> adj = new Dictionary<int, List<int>>();
    
                // create route
                for (int i = 0; i < edges.GetLength(0); i++)
                {
                    CreateRoute(adj, edges[i, 0], edges[i, 1]);
                    CreateRoute(adj, edges[i, 1], edges[i, 0]);
                }
    
                // find leaves
                for (int i = 0; i < n; i++)
                {
                    if (adj.ContainsKey(i) && adj[i].Count == 1)
                    {
                        leaves.Add(i);
                    }
                }
    
                // cut leaves till 1 or 2 are left
                while (n > 2)
                {
                    n -= leaves.Count;
                    List<int> newLeaves = new List<int>();
                    foreach (int i in leaves)
                    {
                        int j = adj[i].Last();
                        adj[j].Remove(i);
                        if (adj[j].Count == 1)
                        {
                            newLeaves.Add(j);
                        }
    
                        leaves = newLeaves;
                    }
                }
    
                return leaves;
            }
    
            private void CreateRoute(Dictionary<int, List<int>> adj, int l, int r)
            {
                if (adj.ContainsKey(l))
                {
                    adj[l].Add(r);
                }
                else
                {
                    adj.Add(l, new List<int>() { r });
                }
            }
    

Log in to reply
 

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