C++ bfs solution by finding the longest path in the tree


  • 0

    Basic idea: the roots of MHT must be the mid points of the longest leaf to leaf path in the tree. And to find the longest path, we can first find the farthest leaf from any node, and then find the farthest leaf from the node found above. Then these two nodes we found are the end points of the longest path. And last, we find the centers of the longest path.

    EDIT: according to @hellotest solution

    class Solution {
    public:
        vector<int> findMinHeightTrees(int n, vector<pair<int, int>>& edges) {
            //find the longest path in the tree
            vector<vector<int>> lists(n);
            for(auto p : edges) {
                lists[p.first].push_back(p.second);
                lists[p.second].push_back(p.first);
            }
            
            int len;
            vector<int> prev(n, 0);
            int f1 = findFarthestLeaf(lists, 0, len, prev);
            int f2 = findFarthestLeaf(lists, f1, len, prev);
    
            //find the mid
            for(int i = 0; i < (len - 1) / 2; ++i) {
                f2 = prev[f2];
            }
            if(len % 2) return vector<int>{f2};
            else return vector<int>{f2, prev[f2]};
        }
        
        int findFarthestLeaf(vector<vector<int>>& lists, int id, int& len, vector<int>& prev) {
            int n = lists.size();
            
            vector<bool> visited(n, 0);
            visited[id] = true;
            prev[id] = id;
            
            queue<int> q;
            q.push(id);
                  
            len = 0;
            int leaf;
            while( !q.empty() ) {
                len++;
                int size = q.size();
                while(size-- > 0) {
                    int f = q.front();
                    q.pop();
                    leaf = f;
                    for (int i : lists[f]) {
                        if (!visited[i]) {
                            visited[i] = true;
                            q.push(i);
                            prev[i] = f;
                        }
                    }
                }
            }
        
            return leaf;
        }
    };
    

  • 1
    H

    @hwf Some improvements for this approach, may not be the best, but at least avoid the second loop to check the dist to find the farthest leaf.

    class Solution {
    public:
        vector<int> findMinHeightTrees(int n, vector<pair<int, int>>& edges) {
            if (n==1) return {0};
            vector<vector<int>> adj(n); 
            vector<int> res;
            for (auto &e : edges) {
                adj[e.first].push_back(e.second);
                adj[e.second].push_back(e.first);
            }
            // two (BFS) traverses to find two ends of the longest path!
            int len=0;
            vector<int> prev(n, 0); // for node i, prev[i] is the previous node along the direction
            int end1 = BFS(adj, 0, len, prev);
            int end2 = BFS(adj, end1, len, prev);
            // find the midpts based on prev info.
            int mid=end2;
            for (int i=1; i<=(len-1)/2; ++i) { // walk (len-1)/2 steps to find mid
                mid = prev[mid];
            }
            res.push_back(mid);
            if ((len & 1)==0) res.push_back(prev[mid]); // len is even
            return res;
        }
    private:
        int BFS(vector<vector<int>>& adj, int start, int& len, vector<int>& prev) {
            // find the farthest leaf starting from start
            int res; // farthest leaf
            len=0; // we will call this function twice so reset it to be 0
            vector<bool> visited(prev.size(), false);
            queue<int> q;
            q.push(start);
            // level order BFS
            int node;
            while (!q.empty()) {
                int size=q.size();
                for (int i=0; i<size; ++i) { // level by level
                    node=q.front();
                    q.pop();
                    visited[node]=true;
                    for (int x : adj[node]) { // check neighbors of node
                        if (visited[x]) continue;
                        prev[x]=node;
                        q.push(x);
                    }
                }
                ++len;
            }
            res=node; // the last visited node will be the farthest leaf
            return res;
        }
    };
    

  • 1
    H

    @hellotest Just for practice purpose, rewrite in DFS without using unordered_set, otherwise DFS part could be further simplified. And it seems pretty annoying to reset some data because we need to call two consecutive DFS.

    class Solution {
    public:
        vector<int> findMinHeightTrees(int n, vector<pair<int, int>>& edges) {
            if (n==1) return {0};
            vector<vector<int>> adj(n); 
            vector<int> res;
            for (auto &e : edges) {
                adj[e.first].push_back(e.second);
                adj[e.second].push_back(e.first);
            }
            // two (DFS) traverses to find two ends of the longest path!
            vector<int> prev(n, 0);
            vector<bool> visited(n, false);
            int depth=0, start=0, end=0;
            DFS(adj, start, end, 0, depth, prev, visited);
            for (int i=0; i<n; ++i) { // reset visited
                visited[i]=false;
            }
            start=end; depth=0; // reset
            DFS(adj, start, end, 0, depth, prev, visited);
            // find the midpts based on prev info.
            int mid=end;
            for (int i=1; i<=(depth-1)/2; ++i) { // walk (depth-1)/2 steps to find mid
                mid = prev[mid];
            }
            res.push_back(mid);
            if ((depth & 1)==0) res.push_back(prev[mid]); // depth is even
            return res;
        }
    private:
        void DFS(vector<vector<int>>& adj, int id, int& end, int level, int& depth, vector<int>& prev, vector<bool>& visited) {
            // preorder recursive
            int res;
            level++;
            visited[id]=true;
            // base case: check whether we reach a leaf, if so update depth
            bool leaf=true;
            for (int x : adj[id]) {
                if (visited[x]==false) leaf=false;
            }
            if (leaf) {
                if (level>depth) {
                    depth=level;
                    end=id;
                }
                return;
            }
            // recursive
            for (int x : adj[id]) {
                if (visited[x]) continue;
                prev[x]=id;
                DFS(adj, x, end, level, depth, prev, visited);
            }
    }
    };
    

Log in to reply
 

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