leetcode261_leetcode261 js解法

两种特殊的情况：有环的存在，有孤独的点的存在
对这两种情况单独存在时候，有个粗暴的判断方式 那就是边的数量为点的数量减1
采用BFS，一层一层的向外扩，用一个集合存储经过的点，最终判断经过点的数量是否为n

public class test {
    public boolean validTree(int n, int[][] edges){
        if(n != edges.length+1){
            return false;
        }
        ArrayList<Integer>[] adj = new ArrayList[n];
        for(int i=0; i<n; i++){
            adj[i] = new ArrayList<>();
        }
        for(int[] edge : edges){
            adj[edge[0]].add(edge[1]);
            adj[edge[1]].add(edge[0]);
        }
        Deque<Integer> queue = new ArrayDeque<>();
        HashSet<Integer> visited = new HashSet<>();
        queue.offer(0);
        visited.add(0);

        while(!queue.isEmpty()){
            int node = queue.poll();
            for(int i : adj[node]){
                if(!visited.contains(i)){
                    queue.add(i);
                    visited.add(i);
                }
            }
        }
        return visited.size() == n;
    }
}
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