DFS 應用範例 II

 DFS 應用範例 II

例 1：判斷二元樹是否為對稱樹

問題描述：檢查二元樹是否為對稱樹，即從根節點到各葉子節點的左右子樹是否鏡像對稱。

DFS 解法：
使用遞迴 DFS 同時遍歷左右子樹，檢查每一層的節點值是否相等且位置對稱。

def is_symmetric(tree):
    def dfs(left, right):
        if left is None and right is None:
            return True
        if left is None or right is None or left != right:
            return False
        return dfs(2 * left + 1, 2 * right + 2) and dfs(2 * left + 2, 2 * right + 1)

    return dfs(1, 2) if tree else True

# 測試
bst = [1, 2, 2, 3, 4, 4, 3]
print("是否為對稱樹:", is_symmetric(bst))  # 預期輸出: True


### 例 2：判斷圖是否有環

**問題描述**：給定無向圖，判斷圖中是否存在環。

**DFS 解法**：
使用 DFS 檢查每個節點是否有回到已訪問的祖先節點的路徑，若存在則有環。

```python
from collections import defaultdict

def has_cycle(graph):
    visited = set()

    def dfs(node, parent):
        visited.add(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                if dfs(neighbor, node):
                    return True
            elif neighbor != parent:
                return True
        return False

    for node in graph:
        if node not in visited:
            if dfs(node, -1):
                return True
    return False

# 測試
graph = defaultdict(list, {0: [1, 2], 1: [0, 3], 2: [0, 3], 3: [1, 2]})
print("圖是否有環:", has_cycle(graph))  # 預期輸出: True


### 例 3：計算島嶼數量 (2D 網格)

**問題描述**：給定一個二維網格，其中 `1` 表示陸地，`0` 表示水域，計算網格中的島嶼數量（連續的 `1` 組成一個島嶼）。

**DFS 解法**：
使用 DFS 遍歷網格，對於每個未訪問過的 `1`，進行遞迴訪問並將其所有相鄰的 `1` 標記為已訪問。

```python
def num_islands(grid):
    if not grid:
        return 0

    rows, cols = len(grid), len(grid[0])
    visited = set()

    def dfs(r, c):
        if r < 0 or c < 0 or r >= rows or c >= cols or grid[r][c] == "0" or (r, c) in visited:
            return
        visited.add((r, c))
        dfs(r + 1, c)
        dfs(r - 1, c)
        dfs(r, c + 1)
        dfs(r, c - 1)

    count = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == "1" and (r, c) not in visited:
                dfs(r, c)
                count += 1
    return count

# 測試
grid = [
  ["1", "1", "0", "0", "0"],
  ["1", "1", "0", "0", "1"],
  ["0", "0", "0", "1", "1"],
  ["0", "0", "0", "0", "0"],
  ["1", "0", "1", "0", "1"]
]
print("島嶼數量:", num_islands(grid))  # 預期輸出: 5