Graph Valid Tree 解題教學:3 種解法完整比較|LeetCode 261 Best Practice

Graph Valid Tree 解題教學示意圖|LeetCode 261

本文完整拆解 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 <= 2000
  • 0 <= edges.length <= 5000
  • edges[i].length == 2
  • 0 <= ai, bi < n
  • ai != 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 演算法步驟

  1. 若邊數不等於 n-1,直接回傳 false。
  2. 用鄰接表建圖。
  3. 從節點 0 出發做 DFS 或 BFS,記錄走訪過的節點數。
  4. 若走訪數等於 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)本文採用