給定
n個節點和一組無向邊edges，判斷這些節點和邊是否構成一棵合法的樹。樹的條件：連通且無環。
Example:
Input: n = 5, edges = [[0,1],[0,2],[0,3],[1,4]] Output: true
Intuition
TIP
合法的樹 = 恰好 n-1 條邊 + 圖連通（或等價地，n-1 條邊 + 無環）。
- 樹的兩個充要條件：(1) 邊數 = n-1 (2) 圖連通
- 先檢查邊數是否為 n-1，不是直接回 false
- 再用 DFS/BFS 或 Union-Find 驗證連通性
Approaches
1. DFS — O(V + E) / O(V + E)
- Idea: 先檢查邊數 = n-1，再從節點 0 做 DFS，確認所有節點都可達
- Time:
O(V + E) - Space:
O(V + E)
class Solution {
fun validTree(n: Int, edges: Array<IntArray>): Boolean {
if (edges.size != n - 1) return false
val graph = Array(n) { mutableListOf<Int>() }
for ((u, v) in edges) {
graph[u].add(v)
graph[v].add(u)
}
val visited = BooleanArray(n)
fun dfs(node: Int) {
visited[node] = true
for (next in graph[node]) {
if (!visited[next]) dfs(next)
}
}
dfs(0)
return visited.all { it }
}
}⭐ 2. Union-Find — O(E * α(n)) / O(n)
- Idea: 先檢查邊數 = n-1，逐條邊 union，若任一邊的兩端已在同一集合則有環（非樹）
- Time:
O(E * α(n)) - Space:
O(n)
class Solution {
private lateinit var parent: IntArray
private lateinit var rank: IntArray
fun validTree(n: Int, edges: Array<IntArray>): Boolean {
if (edges.size != n - 1) return false
parent = IntArray(n) { it }
rank = IntArray(n)
for ((u, v) in edges) {
if (!union(u, v)) return false
}
return true
}
private fun find(x: Int): Int {
if (parent[x] != x) parent[x] = find(parent[x])
return parent[x]
}
private fun union(x: Int, y: Int): Boolean {
val px = find(x)
val py = find(y)
if (px == py) return false
if (rank[px] < rank[py]) parent[px] = py
else if (rank[px] > rank[py]) parent[py] = px
else { parent[py] = px; rank[px]++ }
return true
}
}🔑 Takeaways
- Pattern: 樹的判定 — 邊數 = n-1 + 連通（或無環）
- Key trick: 先檢查
edges.size == n - 1可以提前排除大量不合法情況，簡化後續驗證