C++ Solution. O(n)-Time, O(n)-Space


  • 41
    T

    The basic idea is "keep deleting leaves layer-by-layer, until reach the root."

    Specifically, first find all the leaves, then remove them. After removing, some nodes will become new leaves. So we can continue remove them. Eventually, there is only 1 or 2 nodes left. If there is only one node left, it is the root. If there are 2 nodes, either of them could be a possible root.

    Time Complexity: Since each node will be removed at most once, the complexity is O(n).

    Thanks for pointing out any mistakes.


    Updates:
    More precisely, if the number of nodes is V, and the number of edges is E. The space complexity is O(V+2E), for storing the whole tree. The time complexity is O(E), because we gradually remove all the neighboring information. As some friends pointing out, for a tree, if V=n, then E=n-1. Thus both time complexity and space complexity become O(n).

        class Solution {
        public:
            
            struct Node
            {
                unordered_set<int> neighbor;
                bool isLeaf()const{return neighbor.size()==1;}
            };
            
            vector<int> findMinHeightTrees(int n, vector<pair<int, int>>& edges) {
                
                vector<int> buffer1;
                vector<int> buffer2;
                vector<int>* pB1 = &buffer1;
                vector<int>* pB2 = &buffer2;
                if(n==1)
                {
                    buffer1.push_back(0);
                    return buffer1;
                }
                if(n==2)
                {
                    buffer1.push_back(0);
                    buffer1.push_back(1);
                    return buffer1;
                }
                
                // build the graph
                vector<Node> nodes(n);
                for(auto p:edges)
                {
                    nodes[p.first].neighbor.insert(p.second);
                    nodes[p.second].neighbor.insert(p.first);
                }
                
                // find all leaves
                for(int i=0; i<n; ++i)
                {
                    if(nodes[i].isLeaf()) pB1->push_back(i);
                }
    
                // remove leaves layer-by-layer            
                while(1)
                {
                    for(int i : *pB1)
                    {
                        for(auto n: nodes[i].neighbor)
                        {
                            nodes[n].neighbor.erase(i);
                            if(nodes[n].isLeaf()) pB2->push_back(n);
                        }
                    }
                    if(pB2->empty())
                    {
                        return *pB1;
                    }
                    pB1->clear();
                    swap(pB1, pB2);
                }
                
            }
        };

  • 0
    A

    Great idea! Thanks for sharing!


  • 0
    D
    This post is deleted!

  • 0
    A

    how can the space cost be O(n)?..


  • 0
    T

    O(n) is an approximate answer. Precisely, if the number of nodes is V, and the number of edges is E, the space complexity is O(V+2E). Because we need to store the whole tree.


  • 2

    For a graph with tree characteristics, if V = n then E = n-1.
    Therefore O(n) time O(n) space is not approximate answer. It is the answer.


  • 0
    T

    You are right! Thanks for pointing out!


  • 13
    T

    Similar idea, but uses a queue based implementation instead of swapping two vector pointers. Remove leafs layer by layer until one or two nodes left that are roots of min height.

    vector<int> findMinHeightTrees(int n, vector<pair<int, int>>& edges) {
                    vector<vector<int> > adj_list(n);
                    vector<int> counters(n, 0);
                    for (auto &e : edges) {
                        adj_list[e.first].push_back(e.second);
                        adj_list[e.second].push_back(e.first);
                        ++counters[e.first];
                        ++counters[e.second];
                    }
                    queue<int> q;
                    for (int i = 0; i < n; ++i) {
                        if (counters[i] <= 1) {
                            q.push(i);
                        }
                    }
                    while (n > 2) {
                        int num_leafs = q.size();
                        n -= num_leafs;
                        for (int i = 0; i < num_leafs; ++i) {
                            int node = q.front();
                            q.pop();
                            for (auto neighbor : adj_list[node]) {
                                if (--counters[neighbor] == 1) {
                                    q.push(neighbor);
                                }
                            }
                        }
                    }
                    vector<int> res;
                    while (!q.empty()) {
                        res.push_back(q.front());
                        q.pop();
                    }
                    return res;
                }

  • 1
    Z

    Came up with same idea, with more concise code~

    class Solution {
    public: 
        vector<int> findMinHeightTrees(int n, vector<pair<int, int>>& edges) {
            vector<unordered_set<int>> graph(n);
            for(auto e: edges){
                graph[e.first].insert(e.second);
                graph[e.second].insert(e.first);
            }
            vector<int> degree(n, 0);
            for(int i=0; i<n; i++) degree[i]=graph[i].size();
            for(int i=0, j, remain=n; i<n && remain>2; i++){
                vector<int> del; // nodes to delete
                for(j=0; j<n; j++){
                    if(degree[j]==1) {
                        remain--;
                        del.push_back(j);
                        degree[j]=-1;
                    }
                }
                for(auto k: del){ //delete this node and all connected edges 
                    for(auto neigh: graph[k]) degree[neigh]--;
                }
            }
            vector<int> res;
            for(int i=0; i<n; i++){
                if(degree[i]>=0) res.push_back(i);
            }
            return res;
        }
    };

  • 0
    K

    Good solution! Inspired by your idea and noticed that only the remaining neighbor of a leaf is needed while deleting it, I use an INT to record the xor of one node's all neighbors.
    My code:

    class Solution {
    public:
        vector<int> findMinHeightTrees(int n, vector<pair<int, int>>& edges) {
            vector<int> xor_edges(n,0);
            vector<int> degrees(n,0);
            vector<int> result;
            int edgnum = edges.size();
            if(edgnum == 0){
                result.push_back(0);
                return result;
            }
            for(pair<int,int> e : edges){
                degrees[e.first] ++;
                degrees[e.second] ++;
                xor_edges[e.first] = xor_edges[e.first] ^ e.second;
                xor_edges[e.second] =xor_edges[e.second] ^ e.first;
            }
            int i;
            deque<int> queue;
            for( i=0 ; i<n ; i++){
                if(degrees[i] == 1){
                    queue.push_back(i);
                }
            }
            for( ; edgnum > 1; ){
                queue.push_back(-1);
                for(;;){
                    i = queue.front();
                    queue.pop_front();
                    if(i == -1)break;
                    degrees[i] --;
                    int j = xor_edges[i];
                    //xor_edges[i] = 0;
                    xor_edges[j] ^= i;
                    degrees[j]--;
                    if(degrees[j] == 1){
                        queue.push_back(j);
                    }
                    edgnum--;
                }
            }
            result.insert(result.end(),queue.begin(),queue.end());
            return result;
        }
    
    };

  • 0
    T

    I feel this is O(n^2) b/c you need to go through all the nodes to find out which ones have degree 1.


  • 0
    J

    Nice solution. Only one question: is that necessary to have a for loop in "for (auto neighbor : adj_list[node])"? Because we have already know 'node' can only have one neighbor, then 'adj_list[node].size()' would be always 1. Do I miss something here ?


  • 0
    S

    XOR?
    What if the test case have many nodes or edges?


Log in to reply
 

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