1245. Tree Diameter
Tags:
Medium
Skills:
DFSBFSTreeGraph
June 24, 2025
04:32 AM
No headings found
Loading content...
Related Posts
Leetcode
No headings found
Related Posts
Leetcode
Problem
Tree diameter là độ dài đường đi dài nhất giữa 2 node bất kỳ. Đây là bài toán tối ư trên cây, yêu cầu tìm kiếm sâu/ tần suất trên các node.
Approach
Mindset
Các bước thực hiện
Solution - DFS
SC: O(h), h là chiều cao của cây
1function treeDiameter(edges: number[][]): number {
2 const n = edges.length + 1;
3 const adj: Map<number, number[]> = new Map();
4
5 for (const [u, v] of edges) {
6 if (!adj.has(u)) {
7 adj.set(u, [])
8 }
9 adj.get(u)!.push(v)
10
11 if (!adj.has(v)) {
12 adj.set(v, []);
13 }
14 adj.get(v)!.push(u)
15 }
16
17 let [max_distance, farthest_node] = [0, 0];
18
19 function dfs(current: number, parent: number, depth: number): void {
20 if (depth > max_distance) {
21 max_distance = depth;
22 farthest_node = current;
23 }
24
25 const neighbors = adj.get(current) || [];
26 for (const neighbor of neighbors) {
27 if (neighbor !== parent) {
28 dfs(neighbor, current, depth + 1);
29 }
30 }
31 }
32
33 const start_node = adj.keys().next().value;
34 dfs(start_node, -1, 0);
35
36 max_distance = 0;
37 dfs(farthest_node, -1, 0);
38
39 return max_distance
40}Solution - BFS
1function treeDiameter(edges: number[][]): number {
2 if(edges.length === 0) {
3 return 0
4 }
5
6 const adj: Map<number, number[]> = new Map();
7
8 for(const [u,v] of edges) {
9 if(!adj.has(u)) adj.set(u, []);
10 if(!adj.has(v)) adj.set(v, []);
11
12 adj.get(u)!.push(v);
13 adj.get(v)!.push(u);
14 }
15
16 function bfs(start_node: number): [number, number] {
17 const visited = new Set<number>();
18 let max_dist = 0;
19 let farthest_node = start_node;
20
21 const queue: [number, number][] = [[start_node, 0]];
22 visited.add(start_node);
23
24 while(queue.length > 0) {
25 const [node, dist] = queue.shift()!;
26
27 if(dist > max_dist) {
28 max_dist = dist;
29 farthest_node = node;
30 }
31
32 const neighbors = adj.get(node)! || [];
33 for(const neighbor of neighbors) {
34 if(!visited.has(neighbor)) {
35 visited.add(neighbor)
36 queue.push([neighbor, dist + 1])
37 }
38 }
39 }
40 return [farthest_node, max_dist];
41 }
42
43 const start_node = adj.keys().next().value;
44 const [u] = bfs(start_node);
45
46 const [v, diameter] = bfs(u);
47 return diameter
48}