Diameter of a tree and topological sort

310. Minimum Height Trees

Explanation

For the problem listed here, it is quite interesting as we can:

• use the diameter of a tree template to solve it
• use the topological sort to solve this one.

Using diameter of a tree

Here is my observations:

1. The result at most have two nodes. 1) when the longest path’s length is odd, we have one node as res. 2) when the longest path’s lenght is even, we have two nodes.
2. The result nodes can only exist in the longest path.
3. The longest path is the diameter of the tree
4. The diameter of a tree is a template problem and it can be solved by using two BFSs.

For the diameter of a tree, see diameter of a tree.

Then in order to solve this problem, I used the following technologies:

1. Two bfs to find the diameter
2. Use DFS to find the middle points of the longest path from the start node and end node of the longest path.

C++ code

class Solution {
public:
    int node;
    void bfs(vector<vector<int>>& graph, int n, int firstnode, int& lastnode, int& longestPathLen){
        vector<int> current_level = {firstnode};
        longestPathLen = 0;
        vector<int> seen(n, 0);
        seen[firstnode] = 1;
        while (!current_level.empty()){
            vector<int> next_level;
            for (auto & node: current_level){
                for (auto & nei: graph[node]){
                    if (seen[nei])continue;
                    seen[nei] = 1;
                    next_level.push_back(nei);
                    lastnode = nei;
                }
            }
            current_level = next_level;
            if(!current_level.empty())longestPathLen++;
        }
    }
     void dfs(vector<vector<int>>& graph, int i, int curr, int target_depth, unordered_set<int>&s, vector<int>& seen){
        
         for (auto & nei: graph[i]){
             if (seen[nei] || curr > target_depth) continue;
             seen[nei] = 1;
             if (curr + 1 == target_depth){
                 s.insert(nei);
             }
            dfs(graph, nei, curr + 1, target_depth, s, seen);
         }
     }
    vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
         if (n == 1) return {0};
        vector<vector<int>> graph(n + 1);
        for (auto & e: edges){
            graph[e[0]].push_back(e[1]);
            graph[e[1]].push_back(e[0]);
        }
        // find the diameter of a tree
        int firstnode = 0, lastnode = 0, longestPathLen = 0;
        bfs(graph, n, firstnode, lastnode, longestPathLen);
        firstnode = lastnode;
        longestPathLen = 0;
        bfs(graph, n, firstnode, lastnode, longestPathLen);
        
        
        // find the nodes which has a distance of half of the longest path to the startnode and endnode
        // if the path length is odd, we need find half lenght and half length + 1
        int depth = longestPathLen / 2;
        unordered_set<int> s1, s2;
        vector<int> seen(n, 0);
        dfs(graph, firstnode, 0, depth, s1, seen);
        seen.assign(n, 0);
        dfs(graph, lastnode, 0, depth, s2, seen);
        if (longestPathLen %2 != 0){
            depth ++;
             seen.assign(n, 0);
            dfs(graph, firstnode, 0, depth, s1, seen);
            seen.assign(n, 0);
            dfs(graph, lastnode, 0, depth, s2, seen);
        }
        
        vector<int> ret;
        for (auto& x: s2){
            if (s1.find(x) != s1.end()){
                ret.push_back(x);
            }
        }
        return ret;
        
    }
};

Using topological sort to solve this problem

After the first solution is understood, then we can move to the faster one.

IMAGE IS FROM HERE

If you check the above diagram, it is so cool and clear. Then a topological based solution can jump to your brain if you know this algorithm very well.

C++

const int N = 2e4 + 10;
int indegree[N];
// indicate whether the node is explored or not
int explored[N];
class Solution {
    public:
    vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
        vector<int> ret;
        memset(indegree, 0, sizeof indegree);
        memset(explored, 0, sizeof explored);
        // build the graph
        vector<vector<int>> graph(n);
        for (auto &e: edges)
        {
            indegree[e[0]]++;indegree[e[1]]++;
            graph[e[0]].push_back(e[1]);
            graph[e[1]].push_back(e[0]);
        }
        // explore the graph by using a topological way. 
        // Attention, as the graph is bidirectional,
        // we should explore the indegree with 1 nodes.
        int explored_sofa = 0;
        vector<int> current_level;
        for (int i = 0; i < n; ++i) 
            if(indegree[i] == 1)
                current_level.push_back(i);
        // when the unexploed nodes is 1 or 2, break.
        while (n - explored_sofa > 2)
        {
            vector<int> next_level;
            for (auto & node: current_level)
            {
                explored[node] = 1;
                explored_sofa++;
                for (auto & nei: graph[node])
                {
                    if (--indegree[nei] == 1)
                        next_level.push_back(nei);
                }
            }
            current_level = next_level;
        }
        // the unexplored nodes will be our result.
        for (int i = 0; i < n; ++i)if(!explored[i])ret.push_back(i);
        return ret;
}
};

Thanks for reading.