forked from DaleStudy/leetcode-study
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathhyer0705.ts
More file actions
39 lines (32 loc) · 899 Bytes
/
hyer0705.ts
File metadata and controls
39 lines (32 loc) · 899 Bytes
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
// Time Complexity: O(n)
// Space Complexity: O(n)
export class Solution {
/**
* @param n: An integer
* @param edges: a list of undirected edges
* @return: true if it's a valid tree, or false
*/
validTree(n: number, edges: number[][]): boolean {
if (n === 0) return true;
if (edges.length !== n - 1) return false;
const graph: number[][] = Array.from({ length: n }, () => []);
for (const [s, e] of edges) {
graph[s].push(e);
graph[e].push(s);
}
const visited = new Set<number>();
const queue = [0];
visited.add(0);
let pointer = 0;
while (pointer < queue.length) {
const currentNode = queue[pointer++];
for (const nextNode of graph[currentNode]) {
if (!visited.has(nextNode)) {
queue.push(nextNode);
visited.add(nextNode);
}
}
}
return visited.size === n;
}
}