# 深度優先搜索 (DFS)

深度優先搜索通常使用 Stack (堆疊) 來實現

### 二元樹的深度優先搜索

二元樹的深度優先搜索總共有三種方式

#### 前序遍歷 (preorder traversal)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def __init__(self):
        self.res = []

    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if root:
            self.res.append(root.val)
            if root.left:
                self.preorderTraversal(root.left)
            if root.right:
                self.preorderTraversal(root.right)
        return self.res

#### 中序遍歷 (inorder traversal)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def __init__(self):
        self.res = []

    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if root:
            if root.left:
                self.inorderTraversal(root.left)
            self.res.append(root.val)
            if root.right:
                self.inorderTraversal(root.right)
        return self.res

#### 後序遍歷 (postorder traversal)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def __init__(self):
        self.res = []

    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if root:
            if root.left:
                self.postorderTraversal(root.left)
            if root.right:
                self.postorderTraversal(root.right)
            self.res.append(root.val)
        return self.res

## 圖的深度優先搜索

### 鄰接列表

graph = [[1,2,4],[0,3],[0],[1],[0,5],[4]]
visit = [0] * len(graph)
stack = [0]

while stack:
    node = stack.pop()
    visit[node] = True
    print(node)
    for neighbor in graph[node]:
        if not visit[neighbor]:
            stack.append(neighbor)