https://leetcode.jp/problemdetail.php?id=1245
Given an undirected tree, return its diameter: the number of edges in a longest path in that tree.
The tree is given as an array of
edges where edges[i] = [u, v] is a bidirectional edge between nodes u and v. Each node has labels in the set {0, 1, ..., edges.length}.
Example 1:
Input: edges = [[0,1],[0,2]] Output: 2 Explanation: A longest path of the tree is the path 1 - 0 - 2.
Example 2:
Input: edges = [[0,1],[1,2],[2,3],[1,4],[4,5]] Output: 4 Explanation: A longest path of the tree is the path 3 - 2 - 1 - 4 - 5.
Constraints:
0 <= edges.length < 10^4edges[i][0] != edges[i][1]0 <= edges[i][j] <= edges.length- The given edges form an undirected tree.
(深度优先遍历)
- 根据边集数组建邻接表表示树。
- 我们采用深度优先遍历的方式从
0号点开始遍历。递归函数返回当前结点的最长路径。 - 在遍历当前点的子结点的过程中，我们找到他们递归函数返回值加 1 的最大值和次大值。
- 更新答案最大值加次大值，然后返回最大值。
时间复杂度
- 每个结点仅遍历一次，故时间复杂度为 。
空间复杂度
- 需要额外 的空间存储邻接表。
int ans;
vector<vector<int>> graph;
int dfs(int x, int fa) {
int max1 = 0, max2 = 0;
for (int v : graph[x])
if (v != fa) {
int t = dfs(v, x) + 1;
if (max1 < t) {
max2 = max1;
max1 = t;
} else if (max2 < t) {
max2 = t;
}
}
ans = max(ans, (max1 + max2));
return max1;
}
int treeDiameter(vector<vector<int>>& edges) {
int n = edges.size() + 1;
graph.resize(n);
for (const auto &e : edges) {
graph[e[0]].push_back(e[1]);
graph[e[1]].push_back(e[0]);
}
ans = 0;
dfs(0, -1);
return ans;
}
解题思路：本题是一道图上做有记忆的dfs搜索的题目，是无向图，给定的输入是图的各个边，题目中给出一个关键信息(Each node has labels in the set {0, 1, ..., edges.length})可知图中没有环，如果是有环的图这个题是无解的。最好的证明方法就是反正法，如果有环的话标号最大的节点必然小于边的数量，例如[0, 1], [1, 2], [0, 2], 三个节点且三条边，但编号最大的节点小于边的数量。
作为一个无向不联通图，节点主要分为两种类型，一种可以称为叶节点(这个并非是官方的名字，只是我自己叫着方便)，即只有一个边与它连接，除来叶节点之外的节点则至少有两个边相连。
题目要求找出最长的一个path依次来定义这个tree的直径，很显然直径的选择是从一个叶节点到另外一个叶节点，在构建完图之后找到所有的叶节点，开始进行dfs的遍历，找出其中最长的一条路径来定义树的直径。
这个题目的模型与 568. Maximum Vacation Days 最大的不同是在计算过的值的记忆部分。
在568中每个节点的进与出的部分很清晰的分离，因此只要计算过一次，下一次递归不团从哪个节点进，都返回同样的答案。
本题则需要根据不同的输入返回不同的结果，所以memo的数据结构也不一样，对于每一个节点，需要用一个map来对应该节点到下一个节点的答案。这个地方需要使用map，而不是vector，因为需要使用到下一个节点的序号来索引。如果选择vector，无法将序号转换成下表。
时间复杂度：对于每一个节点而言，图需要计算各个出的值，复杂度为 O(e)
空间复杂度：存储每个节点到每一个方向的值 O(e)
class Solution {
public:
int recursive(vector<vector<int>>& graph, vector<map<int, int>>& memo, vector<bool>& visited, int cur){
int len = 0;
for(int i = 0; i < graph[cur].size(); ++i){
int next = graph[cur][i];
if(!visited[next]){
visited[next] = true;
if(memo[cur][next] == 0){
memo[cur][next] = recursive(graph, memo, visited, next) + 1;
}
len = max(len, memo[cur][next]);
}
}
return len;
}
int treeDiameter(vector<vector<int>>& edges) {
const int nodeCnt = edges.size() + 1;
vector<vector<int>> graph(nodeCnt, vector<int>());
vector<map<int, int>> memo(nodeCnt, map<int, int>()); // map<int, int>: first: the index of next node, second: the value if jump to the node
for(auto edge : edges){
graph[edge[0]].push_back(edge[1]);
graph[edge[1]].push_back(edge[0]);
memo[edge[0]][edge[1]] = 0;
memo[edge[1]][edge[0]] = 0;
}
int ans = 0;
for(int i = 0; i < graph.size(); ++i){
if(graph[i].size() == 1){
vector<bool> visited(nodeCnt, false);
visited[i] = true;
ans = max(ans, recursive(graph, memo, visited, i));
}
}
return ans;
}
};
Method 1: depth – first:
class Solution: def treeDiameter(self, edges: List[List[int]]) -> int: adjacency = collections.defaultdict(set) for i,j in edges: adjacency[i].add(j) adjacency[j].add(i) memo = {} def dfs(i,j): if (i,j) in memo: return memo[i,j] longest = 0 for k in adjacency[j]: if k == i:continue longest = max(longest,dfs(j,k)) memo[(i,j)] = longest + 1 return memo[(i,j)] for i,j in edges: dfs(i,j) dfs(j,i) return max(memo[(i,j)]+memo[(j,i)]-1 for i,j in edges)
Method 2: Breadth – first
class Solution: def treeDiameter(self, edges: List[List[int]]) -> int: adjacency = collections.defaultdict(set) for i,j in edges: adjacency[i].add(j) adjacency[j].add(i) def bfs(node): queue = collections.deque() queue.append((node,0)) memo = {node} while queue: n,long = queue.popleft() for nei in adjacency[n]: if nei not in memo: memo.add(nei) queue.append((nei,long+1)) return n,long far,long = bfs(0) far2,longest = bfs(far) return longest
