本文完整拆解 LeetCode 261 Graph Valid Tree 的解法:從解題思路、演算法步驟到時間與空間複雜度,並整理邊界情況與 3 種解法比較,幫你把 Graph Valid Tree 一次弄懂。
Explore diverse LeetCode solutions in Python, C++, JavaScript, SQL, and TypeScript. Ideal for interview prep, learning, and code practice in multiple programming languages. Github Repo Link
You have a graph of n nodes labeled from 0 to n - 1. You are given an integer n and a list of edges where edges[i] = [ai, bi] indicates that there is an undirected edge between nodes ai and bi in the graph.
Return true if the edges of the given graph make up a valid tree, and false otherwise.
Example 1:

Input: n = 5, edges = [[0,1],[0,2],[0,3],[1,4]] Output: true
Example 2:

Input: n = 5, edges = [[0,1],[1,2],[2,3],[1,3],[1,4]] Output: false
Constraints:
1 <= n <= 20000 <= edges.length <= 5000edges[i].length == 20 <= ai, bi < nai != bi- There are no self-loops or repeated edges.
Python
# time complexity: O(n)
# space complexity: O(n)
from typing import List
class UnionFind:
def __init__(self, n: int) -> None:
self.parents = list(range(n))
def find(self, node: int) -> int:
while node != self.parents[node]:
node = self.parents[node]
return node
def union(self, nodeX: int, nodeY: int) -> bool:
parentX, parentY = self.find(nodeX), self.find(nodeY)
if parentX == parentY:
return False
self.parents[parentX] = parentY
return True
class Solution:
def validTree(self, n: int, edges: List[List[int]]) -> bool:
if len(edges) != n - 1:
return False
disjointUnionSet = UnionFind(n)
for startVertex, endVertex in edges:
if not disjointUnionSet.union(startVertex, endVertex):
return False
return True
n = 5
edges = [[0, 1], [0, 2], [0, 3], [2, 3]]
print(Solution().validTree(n, edges))
Graph Valid Tree 解題思路
一個有 n 個節點的無向圖要是一棵樹,必須同時滿足兩個條件:邊數恰好是 n-1,而且整張圖連通。先檢查邊數可以用 O(1) 擋掉大多數非樹的情況;邊數正確時,只要再確認「從任一點出發能走到所有點」,就不可能存在環。
Graph Valid Tree 演算法步驟
- 若邊數不等於 n-1,直接回傳 false。
- 用鄰接表建圖。
- 從節點 0 出發做 DFS 或 BFS,記錄走訪過的節點數。
- 若走訪數等於 n 就回傳 true,否則代表圖不連通,回傳 false。
Graph Valid Tree 複雜度分析
| 項目 | 複雜度 |
|---|---|
| 時間複雜度 | O(V+E) |
| 空間複雜度 | O(V+E) |
建圖與一次完整走訪各需 O(V+E),時間為 O(V+E)。鄰接表與 visited 佔 O(V+E)。先檢查邊數這一步是 O(1),卻能省下大量無效計算。
Graph Valid Tree 的邊界情況與常見錯誤
- n 為 1 且沒有邊時是合法的樹,要回傳 true。
- 邊數等於 n-1 但圖不連通時,必定同時存在環與孤立塊,所以連通性檢查不可省。
- 無向圖 DFS 要避免走回父節點造成的假環。
- 並查集版本在合併時若發現兩端已同屬一塊,就代表有環。
Graph Valid Tree 其他解法比較
| 解法 | 時間 | 空間 | 說明 |
|---|---|---|---|
| 只檢查有沒有環 | O(V+E) | O(V+E) | 漏掉連通性,會誤判森林 |
| 並查集偵測環 + 計算分量數 | O(E α(V)) | O(V) | 同樣正確且常被使用 |
| 邊數檢查 + 連通性走訪 | O(V+E) | O(V+E) | 本文採用 |
