题解 | #最长路径#

思路：

题目的主要信息：

• n个节点，n-1条边，使之全部连通，这就是一棵树
• 树中任意节点的路径最长值，就是求树的直径

首先我们要知道一个性质：从树的根节点深度优先搜索到最远距离，再从最远距离深度优先搜索到另一最远距离就是树的直径。

方法一：两次深度优先搜索
具体做法：
我们需要用哈希表来存储树的边结构，将树看成图，以权重构建无向图，存入哈希表中。这里便是遍历u v w数组 ，将它们的信息存入哈希表中。
因为dfs下标用到了0和-1，给的数据是节点从1开始的，因此录入哈希表的时候节点序号减1.
再从顶点出发，利用dfs找到最远距离，第二次以当前最远距离再次调用dfs找到最远距离，第二个最远距离即是树的直径。

class Solution {
public:
    struct edge{ //构建边的结构
        int end;
        int weigh;
        edge(int _end, int _weigh): end(_end), weigh(_weigh){}
    };
    //深度优先函数
    void dfs(unordered_map<int, vector<edge>>& graph, vector<long long>& res, int start, int pre, int length){
        vector<edge> edges = graph[start];
        for(int i = 0; i < edges.size(); i++){ //遍历与这个点相连的每一条边
            if(edges[i].end != pre){
                length += edges[i].weigh;
                if(length > res[0]){
                    res[0] = length;
                    res[1] = edges[i].end;
                }
                dfs(graph, res, edges[i].end, start, length);
                length = length - edges[i].weigh; //回溯
            }
        }
    }
    long long solve(int n, vector<int>& u, vector<int>& v, vector<int>& w) {
        unordered_map<int, vector<edge> > graph; //用map构建图，key为顶点编号，vector中记录与之相连的边
        for(int i = 0; i < w.size(); i++){ //遍历边的集合
            int weigh = w[i];
            edge e1 = edge(v[i] - 1, weigh); //在图中将start与end相连
            if(!graph.count(u[i] - 1)){
                vector<edge> temp;
                graph[u[i] - 1] = temp;
            }
            graph[u[i] - 1].push_back(e1);
            edge e2 = edge(u[i] - 1, weigh);
            if(!graph.count(v[i] - 1)){
                vector<edge> temp;
                graph[v[i] - 1] = temp;
            }
            graph[v[i] - 1].push_back(e2);   
        }
        vector<long long> length(2, 0);  //第一个零表示以第0个结点为起点的最长路径长度，第二个零表示最长路径的重点序列
        dfs(graph, length, 0, -1, 0);   //从0结点深度优先找最远距离
        vector<long long> res(2, 0);
        dfs(graph, res, length[1], -1, 0); //以刚刚找到的最远距离再次深度优先找最元距离即是答案
        return res[0];
    }
};

复杂度分析：

• 时间复杂度：，因为使用了unordered_map，只是相当于每个节点访问一次，
• 空间复杂度：，哈希表大小和递归栈最大深度

方法二：两次广度优先搜索
具体做法：
同理，有dfs就会有bfs，同样是两次bfs即可得到树的直径。树的bfs属于层次遍历，于是需要使用队列将子结点压入队列中，后续再依次访问。我们这里为了访问方便，使用矩阵邻接表来表示树。

class Solution {
public:
    int dis[200020];  //记录路径长度
    bool vist[100020]; //访问过的记录，防止重复
    vector<pair<int, int> > vec[100020];  //树两个结点之间的边
    int ans = 0;
    int bfs(int x) //广度优先函数
    {
        memset(vist, 0, sizeof(vist));
        memset(dis, 0, sizeof(dis));
        vist[x] = 1;
        queue<int> q;  //bfs依赖队列，层次遍历
        q.push(x);
        int point = 0;
        int cur_point = x;  //表示当前结点,后面会更新
        while(!q.empty())
        {

            cur_point = q.front();
            q.pop();
            if(dis[cur_point] >= ans) //找最远距离
            {
                ans = dis[cur_point];
                point = cur_point;
            }
            pair<int,int> temp;
            for(int i = 0; i < vec[cur_point].size(); i++)
            {
                temp = vec[cur_point][i];
                if(!vist[temp.first])   //之前没有访问过的点才进入下面
                {
                    vist[temp.first] = true;  //标记访问过的结点
                    dis[temp.first] = temp.second + dis[cur_point];  //相邻点加上当前这条边
                    q.push(temp.first);
                }
            }
        }
        return point;
    }
    long long solve(int n, vector<int>& u, vector<int>& v, vector<int>& w) {
        for(int i = 0; i < w.size(); i++){ //将给的边相连加入v中
            vec[u[i]].push_back(make_pair(v[i], w[i]));
            vec[v[i]].push_back(make_pair(u[i], w[i]));
        }
        int point = bfs(1); //两次bfs
        point = bfs(point);
        return ans;
    }
};

复杂度分析：

• 时间复杂度：，因为使用了邻接矩阵，相当于遍历矩阵
• 空间复杂度：，邻接矩阵的空间及其他辅助数组