你可以假设我们不会给出重复的边在边的列表当中. 无向边 [0, 1] 和 [1, 0] 是同一条边， 因此他们不会同时出现在我们给你的边的列表当中。
输入: n = 5 edges = [[0, 1], [0, 2], [0, 3], [1, 4]]
输出: true.
输入: n = 5 edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]]
输出: false.
public class Solution {
/**
* @param n: An integer
* @param edges: a list of undirected edges
* @return: true if it‘s a valid tree, or false
*/
public boolean validTree(int n, int[][] edges) {
int numOfEdge = edges.length;
// 判断是否为 (n - 1) 条边
if (numOfEdge != n - 1) {
return false;
}
// adjacent[i][j]里存i与j是否相邻
int[][] adjacent = new int[n + 2][n + 2];
for (int i = 0; i < numOfEdge; i++) {
int u = edges[i][0], v = edges[i][1];
adjacent[u][v] = adjacent[v][u] = 1;
}
// visit[i]记录i是否被访问
int[] visit = new int[n + 5];
// 0作为根结点，开始向下遍历
visit[0] = 1;
int root = 0, numOfVisited = 1;
Queue<Integer> q = new LinkedList<Integer>();
q.add(root);
while (!q.isEmpty()) {
root = q.poll();
for (int i = 0; i < n; i++) {
if (adjacent[root][i] != 1) {
continue;
}
// 如果相邻且没有被访问过，说明是儿子，加入队列
if(visit[i] == 0) {
visit[i] = 1;
numOfVisited++;
q.add(i);
}
}
}
if(numOfVisited == n) {
return true;
}
return false;
}
}
