# [LintCode] Graph Valid Tree

http://www.lintcode.com/en/problem/graph-valid-tree/

DFS 解法:

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) {
if (n <= 0 || edges == null || n - 1 != edges.length) {
return false;
}
int[][] matrix = new int[n][n];
Set<Integer> set = new HashSet<Integer>();
for (int i = 0; i < edges.length; i++) {
matrix[edges[i][0]][edges[i][1]] = 1;
matrix[edges[i][1]][edges[i][0]] = 1;
}
dfs(matrix, 0, set);
return set.size() == n;
}

private void dfs(int[][] matrix, int start, Set<Integer> set) {
if (set.contains(start)) {
return;
}
for (int i = 0; i < matrix.length; i++) {
if (matrix[start][i] == 1) {
dfs(matrix, i, set);
}
}
}
}

Union Find 解法：

public class Solution {
/**
* @param n an integer
* @param edges a list of undirected edges
* @return true if it‘s a valid tree, or false
*/
class UnionFind {
int[] id;
int[] weight;
public UnionFind(int n) {
id = new int[n];
weight = new int[n];
for (int i = 0; i < n; i++) {
id[i] = i;
weight[i] = 1;
}
}
public void union(int i, int j) {
int rootI = find(i);
int rootJ = find(j);
if (weight[rootI] < weight[rootJ]) {
id[rootI] = rootJ;
weight[rootJ] += weight[rootI];
} else {
id[rootJ] = rootI;
weight[rootI] += weight[rootJ];
}
}
public int find(int i) {
if (id[i] != i) {
return find(id[i]);
}
return i;
}
}

public boolean validTree(int n, int[][] edges) {
if (n <= 0 || edges == null || n - 1 != edges.length) {
return false;
}
UnionFind uf = new UnionFind(n);
for (int i = 0; i < edges.length; i++) {
if (uf.find(edges[i][0]) == uf.find(edges[i][1])) {
return false;
}
uf.union(edges[i][0], edges[i][1]);
}
return true;
}
}

## Leetcode: Graph Valid Tree &amp;&amp; Summary: Detect cycle in directed graph and undirected graph

Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), write a function to check whether these edges make up a valid tree. For example: Given n = 5 and edges = [[0, 1], [0, 2], [0, 3], [1, 4]], return tru

## [LeetCode#261] Graph Valid Tree

Problem: Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), write a function to check whether these edges make up a valid tree. For example: Given n = 5 and edges = [[0, 1], [0, 2], [0, 3], [1, 4]], r

## [Swift]LeetCode261.图验证树 \$ Graph Valid Tree

Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), write a function to check whether these edges make up a valid tree. For example: Given n = 5 and edges = [[0, 1], [0, 2], [0, 3], [1, 4]], return tru

## Graph Valid Tree

Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), write a function to check whether these edges make up a valid tree. Notice You can assume that no duplicate edges will appear in edges. Since all edg

## Graph Valid Tree -- LeetCode

Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), write a function to check whether these edges make up a valid tree. For example: Given n = 5 and edges = [[0, 1], [0, 2], [0, 3], [1, 4]], return tru

## leetcode 261-Graph Valid Tree(medium)（BFS, DFS, Union find）

Given n nodes labeled from 0 to n-1 and a list of undirected edges (each edge is a pair of nodes), write a function to check whether these edges make up a valid tree. 这道题主要就是判断1.是否有环路 2. 是否是连通图 可以用DFS, BFS 和 Union find,union find最合适. 对于DFS和BFS,首先都是建立

## [LintCode] Flatten Binary Tree to Linked List 将二叉树展开成链表

Flatten a binary tree to a fake "linked list" in pre-order traversal. Here we use the right pointer in TreeNode as the next pointer in ListNode. Notice Don't forget to mark the left child of each node to null. Or you will get Time Limit Exceeded