O(n) time O(n) space solution.


  • 2
    A

    The basic idea

    1 Find the longest path in the tree, start from node T1 to node T2; (first bfs find T1 and the second bfs find T2 also remember the parent path and number of nodes in the longest path. O(n))

    2 Find the middle node/nodes from T2 to T1 (Get from parent path, need to take care of odd even cases, O(n))

    I do not believe this is the best solution. And it takes 1000ms + to finished. Just for sharing!

    class Solution {
    public:
        vector<int> findMinHeightTrees(int n, vector<pair<int, int>>& edges) {
            vector<int> res;
            if (n==0) {
                return res;
            }
            vector<vector<int>> G(n);
            for (const pair<int,int> &edge: edges) {
                G[edge.first].push_back(edge.second);
                G[edge.second].push_back(edge.first);
            }
            queue<int> Q;
            char *visited = new char[n];
            memset(visited, 0, n*sizeof(char));
            int cur = 0;
            Q.push(0);
            while (!Q.empty()) {
                cur = Q.front();
                Q.pop();
                visited[cur] = true;
                for (const int& next : G[cur]) {
                    if (!visited[next]) {
                        Q.push(next);
                    }
                }
            }
            int T1 = cur;
            Q.push(cur);
            memset(visited, 0, n*sizeof(char));
            int *parent = new int[n];
            memset(parent, 0, n*sizeof(int));
            int h = 0;
            while (!Q.empty()) {
                h++;
                int size = Q.size();
                for (int j = 0; j<size; ++j) {
                    cur = Q.front();
                    Q.pop();
                    visited[cur] = true;
                    for (const int& next : G[cur]) {
                        if (!visited[next]) {
                            parent[next] = cur;
                            Q.push(next);
                        }
                    }
                }
            }
            int T2 = cur;
            if (h&1) {
                h/=2;
                for (int i =0;i<h;++i) {
                    T2 = parent[T2];
                }
                res.push_back(T2);
            } else {
                h = h/2 -1;
                for (int i =0;i<h;++i) {
                    T2 = parent[T2];
                }
                res.push_back(T2);
                res.push_back(parent[T2]);
            }
            
            delete[] visited;
            delete[] parent;
            return res;
        }
    };

  • 0
    S

    Good idea.
    Could you explain why one of the most remote node T1 can be found be starting from an arbitrary node?
    Thanks!


  • 0
    T

    T1 is only the most remote point because T2 is, relative to T1. So actually, T1 is arbitrary also. The OP could use two DFS instead and it should be faster.


Log in to reply
 

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