LeetCode 1245 树的直径

地址 https://leetcode-cn.com/contest/biweekly-contest-12/problems/tree-diameter/

给你这棵「无向树」，请你测算并返回它的「直径」：这棵树上最长简单路径的边数。

我们用一个由所有「边」组成的数组 edges 来表示一棵无向树，其中 edges[i] = [u, v] 表示节点 u 和 v 之间的双向边。

树上的节点都已经用 {0, 1, ..., edges.length} 中的数做了标记，每个节点上的标记都是独一无二的。

示例1

输入：edges = [[,],[,]]

输出：

解释：

这棵树上最长的路径是  -  - ，边数为 。

示例2

输入：edges = [[,],[,],[,],[,],[,]]

输出：

解释：

这棵树上最长的路径是  -  -  -  - ，边数为 。

算法1
求无向树最远距离分为两步
1 任选一点 BFS或者DFS获取离该点最远的点
2 以第一步得到的点为起点再次BFS或者DFS获取距离最远的点。两者距离就是最远距离

C++ 代码

 class Solution {

 public:

     pair<int, int> bfs(vector<vector<int>>& e, int start) {

         vector<int> d(e.size(), -);

         queue<int> Q;

         Q.push(start);

         d[start] = ;

         pair<int, int> ret;

         while (!Q.empty()) {

             int x = Q.front();

             Q.pop();

             ret.first = x;

             ret.second = d[x];

             for (auto& y : e[x]) {

                 if (d[y] == -) {

                     d[y] = d[x] + ;

                     Q.push(y);

                 }

             }

         }

         return ret;

     }

     int treeDiameter(vector<vector<int>>& edges) {

         int n = edges.size() + ;

         vector<vector<int>> e(n, vector<int>());

         for (auto& edge: edges) {

             e[edge[]].push_back(edge[]);

             e[edge[]].push_back(edge[]);

         }

         pair<int, int> p;

         p = bfs(e, );

         p = bfs(e, p.first);

         return p.second;

     }

 };

巴特西

LeetCode 1245 树的直径

最新文章

热门文章