深度優先搜尋 (DFS) 解題六例

 使用深度優先搜尋 (DFS) 可以解決各種樹結構和圖結構的問題。以下是使用 DFS 解題的六個例子，涵蓋了常見的應用場景。

---

例 1：求二元樹的最大深度

問題描述：計算二元樹的最大深度，深度是從根節點到最遠葉節點的距離。

DFS 解法：
使用遞迴 DFS 計算每個節點的深度，並取左右子樹的最大深度。

def max_depth(tree, i=0):
    if i >= len(tree) or tree[i] is None:
        return 0
    left_depth = max_depth(tree, 2 * i + 1)
    right_depth = max_depth(tree, 2 * i + 2)
    return 1 + max(left_depth, right_depth)

# 測試
bst = [5, 3, 7, 2, 4, 6, None, 1]
print("二元樹的最大深度:", max_depth(bst))  # 預期輸出: 4

---

例 2：判斷二元樹是否為平衡樹

問題描述：判斷二元樹是否為平衡樹，平衡樹的定義是每個節點的左右子樹高度差不超過 1。

DFS 解法：
使用 DFS 計算每個子樹的高度，如果高度差超過 1 則返回不平衡。

def is_balanced(tree, i=0):
    def dfs_height(index):
        if index >= len(tree) or tree[index] is None:
            return 0
        left_height = dfs_height(2 * index + 1)
        right_height = dfs_height(2 * index + 2)
        if left_height == -1 or right_height == -1 or abs(left_height - right_height) > 1:
            return -1  # 表示不平衡
        return 1 + max(left_height, right_height)

    return dfs_height(i) != -1

# 測試
print("是否為平衡樹:", is_balanced(bst))  # 預期輸出: True

---

例 3：計算二元樹的所有根到葉的路徑

問題描述：列出二元樹中所有從根到葉的路徑。

DFS 解法：
使用 DFS 遞迴從根訪問到葉子節點，每到一個葉節點就保存當前路徑。

def all_paths(tree):
    def dfs(i, path, result):
        if i >= len(tree) or tree[i] is None:
            return
        path.append(tree[i])
        # 如果是葉節點，將當前路徑加入結果
        if 2 * i + 1 >= len(tree) or (tree[2 * i + 1] is None and tree[2 * i + 2] is None):
            result.append(list(path))
        else:
            dfs(2 * i + 1, path, result)  # 左子樹
            dfs(2 * i + 2, path, result)  # 右子樹
        path.pop()

    result = []
    dfs(0, [], result)
    return result

# 測試
print("所有根到葉的路徑:", all_paths(bst))  # 預期輸出: [[5, 3, 2, 1], [5, 3, 4], [5, 7, 6]]

---

例 4：計算二元樹中的節點總數

問題描述：計算二元樹中節點的總數。

DFS 解法：
使用 DFS 訪問每個節點並累加計數。

def count_nodes(tree, i=0):
    if i >= len(tree) or tree[i] is None:
        return 0
    return 1 + count_nodes(tree, 2 * i + 1) + count_nodes(tree, 2 * i + 2)

# 測試
print("節點總數:", count_nodes(bst))  # 預期輸出: 6

---

例 5：計算二元樹中所有葉子節點的和

問題描述：計算二元樹中所有葉子節點的數值和。

DFS 解法：
使用 DFS 遞迴訪問每個節點，若是葉子節點則加到總和中。

def sum_leaves(tree, i=0):
    if i >= len(tree) or tree[i] is None:
        return 0
    # 若為葉節點
    if (2 * i + 1 >= len(tree) or tree[2 * i + 1] is None) and (2 * i + 2 >= len(tree) or tree[2 * i + 2] is None):
        return tree[i]
    return sum_leaves(tree, 2 * i + 1) + sum_leaves(tree, 2 * i + 2)

# 測試
print("所有葉子節點的和:", sum_leaves(bst))  # 預期輸出: 1 + 4 + 6 = 11

---

例 6：檢查二元樹是否包含某條根到葉的路徑，其和等於指定值

問題描述：檢查是否存在一條從根到葉的路徑，使得該路徑上所有節點的和等於給定值。

DFS 解法：
在遞迴過程中，減去當前節點的值，當達到葉子節點且剩餘的和為 0 時，則存在該路徑。

def has_path_sum(tree, target, i=0):
    if i >= len(tree) or tree[i] is None:
        return False
    # 若是葉節點且剩餘和剛好為 0，則找到目標路徑
    if (2 * i + 1 >= len(tree) or tree[2 * i + 1] is None) and (2 * i + 2 >= len(tree) or tree[2 * i + 2] is None):
        return target == tree[i]
    # 遞迴檢查左右子樹
    return has_path_sum(tree, target - tree[i], 2 * i + 1) or has_path_sum(tree, target - tree[i], 2 * i + 2)

# 測試
print("是否存在和為 10 的根到葉路徑:", has_path_sum(bst, 10))  # 預期輸出: True
print("是否存在和為 15 的根到葉路徑:", has_path_sum(bst, 15))  # 預期輸出: False