Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/1245.html
1245. Tree Diameter
Level
Medium
Description
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^4
edges[i][0] != edges[i][1]
0 <= edges[i][j] <= edges.length
- The given edges form an undirected tree.
Solution
For each node, obtain its number of degrees, which is the number of nodes that the node directly connects to, and all the neighbors of the node.
Do breadth first search starting from the nodes with degree 1. Each time a node is visited, decrease its degree by 1, obtain all its neighbors, and decrease each neighbor’s degree by 1. If a neighbor’s degree becomes 1, then offer the neighbor to the queue for the next step’s search. During the search, maintain the depth of the search.
Finally, there will be 1 node or 2 nodes remaining. If there is 1 node remaining, then the diameter is twice the depth. If there are 2 nodes remaining, then there is an edge that connects the 2 nodes, so the diameter is twice the depth plus 1.
-
class Solution { public int treeDiameter(int[][] edges) { int nodes = edges.length + 1; int[] degrees = new int[nodes]; Set<Integer>[] connects = new Set[nodes]; for (int i = 0; i < nodes; i++) connects[i] = new HashSet<Integer>(); for (int[] edge : edges) { int node1 = edge[0], node2 = edge[1]; degrees[node1]++; degrees[node2]++; connects[node1].add(node2); connects[node2].add(node1); } Queue<Integer> queue = new LinkedList<Integer>(); for (int i = 0; i < nodes; i++) { if (degrees[i] == 1) queue.offer(i); } int depth = 0; int remaining = nodes; while (!queue.isEmpty() && remaining > 2) { int size = queue.size(); for (int i = 0; i < size; i++) { int node = queue.poll(); degrees[node]--; Set<Integer> connectSet = connects[node]; for (int connect : connectSet) { degrees[connect]--; if (degrees[connect] == 1) queue.offer(connect); } } remaining -= size; depth++; } return remaining == 2 ? 2 * depth + 1 : 2 * depth; } }
-
// OJ: https://leetcode.com/problems/tree-diameter/ // Time: O(N) // Space: O(N) class Solution { public: int treeDiameter(vector<vector<int>>& E) { int N = E.size() + 1, step = 0; vector<vector<int>> G(N); vector<int> indegree(N); for (auto &e : E) { G[e[0]].push_back(e[1]); G[e[1]].push_back(e[0]); indegree[e[0]]++; indegree[e[1]]++; } queue<int> q; for (int i = 0; i < N; ++i) { if (indegree[i] == 1) q.push(i); } while (q.size() > 1) { int cnt = q.size(); while (cnt--) { int u = q.front(); q.pop(); --indegree[u]; for (int v : G[u]) { if (indegree[v] == 0) continue; if (--indegree[v] == 1) { q.push(v); } } } ++step; } return step * 2 + q.size() - 1; } };
-
class Solution: def treeDiameter(self, edges: List[List[int]]) -> int: def dfs(u, t): nonlocal ans, vis, d, next if vis[u]: return vis[u] = True for v in d[u]: dfs(v, t + 1) if ans < t: ans = t next = u d = defaultdict(set) vis = [False] * (len(edges) + 1) for u, v in edges: d[u].add(v) d[v].add(u) ans = 0 next = 0 dfs(edges[0][0], 0) vis = [False] * (len(edges) + 1) dfs(next, 0) return ans
-
func treeDiameter(edges [][]int) int { n := len(edges) g := make(map[int][]int) for _, e := range edges { g[e[0]] = append(g[e[0]], e[1]) g[e[1]] = append(g[e[1]], e[0]) } vis := make(map[int]bool, n+1) ans := 0 next := edges[0][0] var dfs func(u, t int) dfs = func(u, t int) { if vis[u] { return } vis[u] = true if ans < t { ans = t next = u } if vs, ok := g[u]; ok { for _, v := range vs { dfs(v, t+1) } } } dfs(next, 0) vis = make(map[int]bool, n+1) dfs(next, 0) return ans }