C# - Find max distance leaves and path mid point - O(n)


  • 1

    Find the farthest apart leaves on the tree. Do this by starting with any vertex and find it's farthest leaf. Then take that leaf and find the farthest vertex from it. Now you have the 2 farthest leaves on the tree. Find the path between them and take the middle 1 or 2 vertices depending on odd or even count in path.

        public IList<int> FindMinHeightTrees(int n, int[,] edges) 
        {
            List<int>[] nodes = new List<int>[n];
            for (int i = 0; i < n; i++) nodes[i] = new List<int>();
            
            // build undirected graph
            for (int i = 0; i < edges.GetLength(0); i++)
            {
                nodes[edges[i,0]].Add(edges[i,1]);
                nodes[edges[i,1]].Add(edges[i,0]);
            }
            
            // Farthest() return value is 2 ints
            //   int[0] - distance to farther node
            //   int[1] - the farthest node
            int[] leaf1 = Farthest(0, nodes, -1, 1); // start at any node
            int[] leaf2 = Farthest(leaf1[1], nodes, -1, 1);  // farthest leaves
            
            List<int> path = new List<int>();
            FindPath(leaf1[1], nodes, -1, leaf2[1], path);
            
            int mid = leaf2[0]/2;
            IList<int> res = new List<int>() { path[mid] };
            if (leaf2[0] % 2 == 0) res.Add(path[mid - 1]); // even length path has 2 middle nodes
            return res;
        }
    
        public void FindPath(int node, List<int>[] nodes, int from, int end, List<int> path)
        {
            if (path.Count > 0 && path[path.Count - 1] == end) return;
            
            path.Add(node);
            foreach (int c in nodes[node])
            {
                if (c != from)
                {
                    FindPath(c, nodes, node, end, path);
                }
            }
            
            if (path[path.Count - 1] == end) return;
            else path.RemoveAt(path.Count - 1);
        }
    
        // return value is 2 ints
        //   int[0] - distance to farther node
        //   int[1] - the farthest node
        public int[] Farthest(int node, List<int>[] nodes, int from, int distance)
        {
            int[] max = new int[] { distance, node };
            foreach (int c in nodes[node])
            {
                if (c != from)
                {
                    int[] f = Farthest(c, nodes, node, distance + 1);
                    if (f[0] > max[0]) max = f;
                }
            }
            
            return max;
        }
    

Log in to reply
 

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