LeetCode 310. Minimum Height Trees (DFS)

ShenduCC

发布于 2020-06-10 10:33:53

2580

发布于 2020-06-10 10:33:53

文章被收录于专栏：算法修养

题目

给你一个无向无环图，这个图的任何一个节点都可以当成一个树的根节点。让你找到形成的树的高度最小的那几个根节点。

首先，这个根节点要么只有1个，要么只有2个。而且就在图中最长的一条路径上，如果这个路径上的节点数为偶数，那就是2个，否则就是1个

那么怎么找这条最长路径呢？首先从任意一个点出发，找到离它最远的点t1,然后从t1出发找到离它最远的点t2,t1和t2就是最长的路径上的两个端点

class Solution {
public:
    
vector<int> edge[100005];
int vis[100005];
int t1, t2;
int d1, d2;
int path[100005];
int pos;
int ans1, ans2;
vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {

    vector<int> ans;
    if (edges.size() == 0)
        return ans;
    
    for(int i=0;i<n;i++)
    {
        v.push_back(edge);
    }
    for (int i = 0; i < edges.size(); i++)
    {
        edge[edges[i][0]].push_back(edges[i][1]);
        edge[edges[i][1]].push_back(edges[i][0]);
    }

    ans2 = -1;
    pos = 0;
    d1 = d2 = 0;
    memset(vis,0,sizeof(vis));
    vis[0]=1;
    DFS(0, 1);
    path[pos++] = t1;
    memset(vis,0,sizeof(vis));
    vis[t1]=1;
    DFS2(t1, 1);
    ans.push_back(ans1);
    if (ans2 != -1)
        ans.push_back(ans2);

    return ans;

}

void DFS(int node,int deep)
{
    if (d1 < deep)
    {
        d1 = deep;
        t1 = node;
    }
    for (int i = 0; i < edge[node].size(); i++)
    {
        if(vis[edge[node][i]])
            continue;
        vis[edge[node][i]]=1;
        DFS(edge[node][i], deep + 1);
    
    }
}

void DFS2(int node, int deep)
{
    
    if (d2 < deep)
    {
        if (pos & 1)
        {
            ans1 = path[pos / 2];
            ans2 = -1;
        }
        else
        {
            ans2 = path[pos / 2];
            ans1 = path[pos / 2 - 1];
        }
        d2 = deep;
    }

    for (int i = 0; i < edge[node].size(); i++)
    {
        if(vis[edge[node][i]])
            continue;
        vis[edge[node][i]]=1;
        path[pos++] = edge[node][i];
        DFS2(edge[node][i], deep + 1);
        pos--;
    }
}

};

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2020-06-08 ，如有侵权请联系 cloudcommunity@tencent.com 删除

dfs