树与图的遍历

from typing import Optional


class TreeNode:
    def __init__(self, val: int, left=None, right=None):
        self.val = val
        self.left: Optional["TreeNode"] = left
        self.right: Optional["TreeNode"] = right


def inorder_recursive(root: Optional[TreeNode]) -> list[int]:
    """递归版：访问顺序 = 左 -> 根 -> 右。"""
    result: list[int] = []

    def dfs(node: Optional[TreeNode]) -> None:
        if node is None:          # 空节点是递归的终止条件
            return
        dfs(node.left)            # 先把整棵左子树走完
        result.append(node.val)   # 回到根，记录根的值（中序的"中"）
        dfs(node.right)           # 再把整棵右子树走完

    dfs(root)
    return result


def inorder_iterative(root: Optional[TreeNode]) -> list[int]:
    """迭代版：用一个显式栈替代递归调用栈。"""
    result: list[int] = []
    stack: list[TreeNode] = []
    node = root
    while node is not None or stack:
        while node is not None:   # 对应 dfs(node.left)：一路向左压栈
            stack.append(node)
            node = node.left
        node = stack.pop()        # 栈顶是当前最左、尚未访问的节点
        result.append(node.val)   # 访问它（对应 result.append）
        node = node.right         # 转向右子树（对应 dfs(node.right)）
    return result


if __name__ == "__main__":
    #        4
    #       / \
    #      2   6
    #     / \ / \
    #    1  3 5  7   —— 一棵 BST
    root = TreeNode(4,
                    TreeNode(2, TreeNode(1), TreeNode(3)),
                    TreeNode(6, TreeNode(5), TreeNode(7)))
    print(inorder_recursive(root))   # [1, 2, 3, 4, 5, 6, 7]
    print(inorder_iterative(root))   # [1, 2, 3, 4, 5, 6, 7] —— 有序，证明是 BST

def num_islands(grid: list[list[str]]) -> int:
    if not grid:
        return 0
    rows, cols = len(grid), len(grid[0])

    def dfs(r: int, c: int) -> None:
        # 越界，或是水，或已淹没 —— 直接返回（递归终止条件）
        if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] != "1":
            return
        grid[r][c] = "0"          # 把当前陆地"淹没"，等价于标记 visited
        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":  # 碰到一块没淹没的陆地
                count += 1          # 发现一座新岛
                dfs(r, c)           # 淹没它的整片连通块
    return count


if __name__ == "__main__":
    grid = [
        ["1", "1", "0", "0", "0"],
        ["1", "1", "0", "0", "0"],
        ["0", "0", "1", "0", "0"],
        ["0", "0", "0", "1", "1"],
    ]
    print(num_islands(grid))  # 3

from collections import deque


def shortest_path(grid: list[list[int]]) -> int:
    """返回从 (0,0) 到右下角的最短步数；不可达返回 -1。"""
    rows, cols = len(grid), len(grid[0])
    if grid[0][0] != 0 or grid[rows - 1][cols - 1] != 0:
        return -1

    queue: deque[tuple[int, int, int]] = deque()
    queue.append((0, 0, 0))       # (行, 列, 已走步数)
    visited = {(0, 0)}            # visited 防止节点重复入队

    while queue:
        r, c, steps = queue.popleft()   # FIFO：先入队的先出队，保证按层处理
        if (r, c) == (rows - 1, cols - 1):
            return steps                # 第一次到达终点 = 最短步数
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            nr, nc = r + dr, c + dc
            if (0 <= nr < rows and 0 <= nc < cols
                    and grid[nr][nc] == 0 and (nr, nc) not in visited):
                visited.add((nr, nc))   # 入队前就标记，避免同一格被多次入队
                queue.append((nr, nc, steps + 1))
    return -1


if __name__ == "__main__":
    grid = [
        [0, 0, 1, 0],
        [1, 0, 1, 0],
        [0, 0, 0, 0],
        [0, 1, 1, 0],
    ]
    print(shortest_path(grid))  # 6

def permute(nums: list[int]) -> list[list[int]]:
    result: list[list[int]] = []
    path: list[int] = []                 # 当前正在构造的排列
    used = [False] * len(nums)           # used[i] 标记 nums[i] 是否已在 path 中

    def backtrack() -> None:
        if len(path) == len(nums):       # 路径填满 = 一个完整排列
            result.append(path[:])       # 存副本：path 后面还会被改动
            return
        for i in range(len(nums)):
            if used[i]:                  # 剪枝：这个数已经用过，跳过该分支
                continue
            path.append(nums[i])         # 选择：把 nums[i] 放进路径
            used[i] = True
            backtrack()                  # 递归：去填下一位
            path.pop()                   # 撤销：把 nums[i] 拿出路径
            used[i] = False              # 撤销：标记回未用，供别的分支复用

    backtrack()
    return result


if __name__ == "__main__":
    print(permute([1, 2, 3]))
    # [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

from collections import deque


def graph_dfs(graph: dict[int, list[int]], start: int) -> list[int]:
    """邻接表上的 DFS，返回访问顺序。"""
    order: list[int] = []
    visited: set[int] = set()

    def dfs(node: int) -> None:
        visited.add(node)             # 进入即标记，防止有环时重复访问
        order.append(node)
        for nxt in graph[node]:       # 扫这个节点的邻居列表（邻接表 O(degree)）
            if nxt not in visited:
                dfs(nxt)

    dfs(start)
    return order


def graph_bfs(graph: dict[int, list[int]], start: int) -> list[int]:
    """邻接表上的 BFS，返回访问顺序。"""
    order: list[int] = []
    visited = {start}                 # 入队前就标记，避免同一点多次入队
    queue: deque[int] = deque([start])
    while queue:
        node = queue.popleft()        # FIFO：保证按层（按距离）访问
        order.append(node)
        for nxt in graph[node]:
            if nxt not in visited:
                visited.add(nxt)
                queue.append(nxt)
    return order


if __name__ == "__main__":
    #  0 — 1 — 3
    #  |   |
    #  2 —-+      （含环 0-1-2-0）
    g = {0: [1, 2], 1: [0, 3, 2], 2: [0, 1], 3: [1]}
    print(graph_dfs(g, 0))  # [0, 1, 3, 2]
    print(graph_bfs(g, 0))  # [0, 1, 2, 3]