DFS with backtracking. 96ms


  • 1
    Y

    DFS with backtracking.
    The first pass of dfs choose '0' as the root, and find the farthest leaf 'point' from the node. The second pass choose 'point' as the root, and find the farthest leaf while record the path from the root 'point' to the farthest leaf by using backtracking.
    And the answer is the middle of this path.

    class Solution {
    private:
        int point;
    public:
        void dfs(int n, vector<int>& parent, vector<bool>& visited, vector<vector<int>>& lnklst, int l, int& maxl){
            visited[n]=true;
            for(int i=0;i<lnklst[n].size();i++){
                int k=lnklst[n][i];
                if(visited[k]==true)
                    continue;
                else{
                    parent[k]=n;
                    visited[k]=true;
                    if(l>maxl){
                        maxl=l;
                        point=k;
                    }
                    dfs(k,parent,visited,lnklst,l+1,maxl);
                }
            }
        }
        vector<int> findMinHeightTrees(int n, vector<pair<int, int>>& edges) {
            vector<vector<int>>lnklst(n);
            vector<bool>visited(n,false);
            vector<int>parent(n,0);
            int maxl=0;
            vector<int>result;
            int min=INT_MAX;
            for(int i=0;i<edges.size();i++){
                lnklst[edges[i].first].push_back(edges[i].second);
                lnklst[edges[i].second].push_back(edges[i].first);
            }
            dfs(0,parent,visited,lnklst,1,maxl);
            parent.assign(n,0);
            visited.assign(n,false);
            maxl=0;
            dfs(point,parent,visited,lnklst,1,maxl);
            if(maxl%2==0){
                for(int i=0;i<maxl/2;i++)
                    point=parent[point];
                result.push_back(point);
            }
            else{
                for(int i=0;i<maxl/2;i++)
                    point=parent[point];
                result.push_back(point);
                point=parent[point];
                result.push_back(point);
            }
            return result;
        }
    };
    

  • 0
    N

    the adjact List is very efficient! good.


  • 0
    O
    This post is deleted!

Log in to reply
 

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