搜索与遍历的核心理解#

什么是遍历#

遍历强调的是"把结构里的节点都走一遍"。树的前中后序、层序遍历，图里的连通块遍历，本质都是按照某种顺序访问节点，并在访问过程中收集信息。

什么是搜索#

搜索强调的是"在状态空间中找答案"。它不一定要访问所有节点，而是根据题目的目标、约束和剪枝条件，尝试从当前状态转移到下一个状态。比如找路径、找最短步数、枚举所有方案、判断是否存在某种状态。

遍历和搜索的区别#

遍历更像"按结构走完"，搜索更像"带目标地尝试"。很多题二者会重叠：DFS/BFS 既可以是遍历方式，也可以是搜索策略。做题时重点不是纠结名字，而是先判断：状态是什么、选择是什么、什么时候停止、是否需要撤销选择。

DFS 和 BFS 的区别#

DFS 是一条路走到底，天然适合递归、回溯、连通性、枚举方案、判断环。BFS 是一层一层扩散，天然适合无权图最短路、最少步数、多源扩散。

什么时候想到 DFS#

看到"所有路径""所有方案""能不能到达""连通块数量""从当前状态继续往下试""需要回溯撤销选择"，优先考虑 DFS。

什么时候想到 BFS#

看到"最短路径""最少步数""一圈一圈扩散""同时从多个源头开始""无权图距离"，优先考虑 BFS。

搜索题里的状态、选择、路径、剪枝#

搜索题可以拆成四个词：

状态：当前递归或队列里保存的信息，比如坐标、节点、当前字符串、剩余目标。
选择：从当前状态能走向哪些下一状态。
路径：从起点走到当前状态经过的内容，回溯题里通常用 path 维护。
剪枝：发现当前状态不可能得到答案时提前返回，比如越界、重复访问、超过目标值、前缀不存在。

visited 的作用#

visited 的核心作用是防止重复访问，但要注意它有两种语义：

全局 visited：一个节点访问过就不再访问，常见于图遍历、岛屿淹没。
路径级 visited：只限制当前路径不能重复使用，回溯结束后要撤销，常见于单词搜索、排列。

能不能原地修改数组，本质上取决于修改后会不会破坏题目的判断语义。比如岛屿面积可以把陆地改成水，但岛屿周长不能把访问过的陆地改成水，否则会把相邻陆地误算成水边。

Python 中常用的数据结构#

栈/递归：DFS。
deque：BFS 队列。
set：去重、visited、快速判断。
dict：邻接表、映射、Trie 子节点。
list[list[int]]：网格、邻接矩阵、动态维护棋盘。

树的遍历：按结构走完整棵树#

二叉树遍历的核心理解#

前序遍历#

LC144 - 二叉树的前序遍历#

三种遍历感觉写过一百遍了，肌肉记忆吧

Python3 点击展开代码

10 lines 展开代码

def solution(root:TreeNode):
    ans = []
    def dfs(node):
        if not node:
            return
        ans.append(node.val)
        dfs(node.left)
        dfs(node.right)
    dfs(root)
    return ans

中序遍历#

LC94 - 二叉树的中序遍历#

Python3 点击展开代码

10 lines 展开代码

def solution(root:TreeNode):
    ans = []
    def dfs(node):
        if not node:
            return
        dfs(node.left)
        ans.append(node.val)
        dfs(node.right)
    dfs(root)
    return ans

后序遍历#

LC145 - 二叉树的后序遍历#

Python3 点击展开代码

10 lines 展开代码

def solution(root:TreeNode):
    ans = []
    def dfs(node):
        if not node:
            return
        dfs(node.left)
        dfs(node.right)
        ans.append(node.val)
    dfs(root)
    return ans

层序遍历#

LC102 - 二叉树的层序遍历#

依旧肌肉记忆

Python3 点击展开代码

17 lines 展开代码

def solution(root:TreeNode):
    if not root:
        return []
    q = deque([root])
    ans = []
    while q:
        sz = len(q)
        level = []
        for _ in range(sz):
            node = q.popleft()
            level.append(node.val)
            if node.left:
                q.append(node.left)
            if node.right:
                q.append(node.right)
        ans.append(level)
    return ans

LC107 - 二叉树的层序遍历 II#

直接返回的时候reverse一下。。

LC103 - 二叉树的锯齿形层序遍历#

用当len(ans)%2 == 0时候为奇数层，偶数层appendleft。其他不用说了。

LC199 - 二叉树的右视图#

每次取队列的-1位置加入答案。就改一行ans.append(level[-1])。

N 叉树遍历#

LC589 - N 叉树的前序遍历#

稍微推广一下即可。

Python3 点击展开代码

10 lines 展开代码

def solution(root:TreeNode):
    ans = []
    def dfs(node):
        if not node:
            return 
        ans.append(node.val)
        for child in node.children:
            dfs(child)
    dfs(root)
    return ans

LC590 - N 叉树的后序遍历#

Python3 点击展开代码

10 lines 展开代码

def solution(root:TreeNode):
    ans = []
    def dfs(node):
        if not node:
            return 
        for child in node.children:
            dfs(child)
        ans.append(node.val)
    dfs(root)
    return ans

LC429 - N 叉树的层序遍历#

几乎跟二叉树没啥变化

Python3 点击展开代码

16 lines 展开代码

def solution(root:TreeNode):
    if not root:
        return []
    q = deque([root])
    ans = []
    while q:
        sz = len(q)
        level = []
        for _ in range(sz):
            node = q.popleft()
            level.append(node.val)
            if node.children:
                for child in node.children:
                    q.append(child)
        ans.append(level)
    return ans

树遍历常见模板#

树的 DFS 模板核心是：

Python3 点击展开代码

8 lines 展开代码

def dfs(node):
    if not node:
        return
    # 前序位置
    dfs(node.left)
    # 中序位置
    dfs(node.right)
    # 后序位置

树的 BFS 模板核心是：

Python3 点击展开代码

10 lines 展开代码

from collections import deque

q = deque([root])
while q:
    for _ in range(len(q)):
        node = q.popleft()
        if node.left:
            q.append(node.left)
        if node.right:
            q.append(node.right)

DFS 搜索：一条路走到底#

DFS 的核心思想#

DFS 的核心是"沿着一个方向不断深入，走不动再回退"。递归写法里，每一层函数都代表一个状态，函数内部枚举下一步选择。

递归 DFS#

递归 DFS 最重要的是三件事：

递归入口表示什么状态。
递归出口什么时候停止。
当前状态如何转移到下一状态。

迭代 DFS#

迭代 DFS 用栈模拟递归。普通遍历可以写，但回溯题里递归通常更自然，因为递归栈天然保存了路径。

DFS 中的 visited#

图和网格 DFS 通常需要 visited 或原地标记，否则可能在环里来回走。树结构天然没有回边，一般不需要 visited。

DFS 中的前序位置和后序位置#

前序位置适合"进入节点时处理"，比如记录路径、标记访问。后序位置适合"处理完子问题后汇总"，比如树形 DP、课程表 DFS 拓扑排序、回溯撤销选择。

图的连通性搜索#

LC841 - 钥匙和房间#

我们将每个房间看做一个节点，房间里面的钥匙指向别的房间，相当于一条边。所以这题，其实就是从0号房间开始搜索，看最终能访问到多少个节点。

Python3 点击展开代码

15 lines 展开代码

def canVisitAllRooms(self, rooms: list[list[int]]) -> bool:
    # 如果从一个房间出发，能搜到底，全部加入visited，就返回True
    # 由于房间选择可能不同，使用dfs
    n = len(rooms)
    visited = set()
    def dfs(i):
        # 如果已经访问过了，出口
        if i in visited:
            return 
        # 否则，标记，并且遍历下一个情况
        visited.add(i)
        for room in rooms[i]:
            dfs(room)
    dfs(0)
    return len(rooms) == len(visited)

当然，这一题也可以bfs来做。因为如果要访问完毕所有房间，那么最终路径长度一定是房间长度。所以我们可以bfs到底看看能不能走那么远即可：

Python3 点击展开代码

16 lines 展开代码

from collections import deque

def canVisitAllRooms(self, rooms: list[list[int]]) -> bool:
    n = len(rooms)
    visited = set()
    # 从0开始bfs
    visited.add(0)
    q = deque([0])
    while q:
        curr = q.popleft()
        for key in rooms[curr]:
            # BFS要防止回搜，dfs可以在递归处来防，bfs必须在这里防
            if key not in visited:
                visited.add(key)
                q.append(key)
    return len(visited) == n

LC547 - 省份数量#

其实就是给一个邻接矩阵，找连通块数量。最常用方法是统计 DFS 启动次数。

Python3 点击展开代码

17 lines 展开代码

def findCircleNum(self, isConnected: list[list[int]]) -> int:
    n = len(isConnected)
    visited = set()

    def dfs(city: int) -> None:
        visited.add(city)
        for nxt in range(n):
            if isConnected[city][nxt] == 1 and nxt not in visited:
                dfs(nxt)

    count = 0
    for city in range(n):
        if city not in visited:
            dfs(city)
            count += 1

    return count

LC1971 - 寻找图中是否存在路径#

听名字就知道要dfs了，它问有一个具有 n 个顶点的双向图，其中每个顶点标记从 0 到 n - 1（包含 0 和 n - 1）。图中的边用一个二维整数数组 edges 表示，其中 edges[i] = [ui, vi] 表示顶点 ui 和顶点 vi 之间的双向边。每个顶点对由最多一条边连接，并且没有顶点存在与自身相连的边。请你确定是否存在从顶点 source 开始，到顶点 destination 结束的有效路径。

我们直接从source走一次dfs即可，如果遇到目标节点就返回True，否则返回False。

这一题考一下邻接表的写法。

Python3 点击展开代码

17 lines 展开代码

def validPath(self, n: int, edges: list[list[int]], source: int, destination: int) -> bool:
    # 建立邻接表
    graph = [[] for _ in range(n)]
    for edge in edges:
        graph[edge[0]].append(edge[1])
        graph[edge[1]].append(edge[0])

    # 写dfs函数
    visited = set()
    def dfs(node):
        if node in visited:
            return 
        visited.add(node)
        for nxt in graph[node]:
            dfs(nxt)
    dfs(source)
    return destination in visited

这一题只要找到就可以返回了，所以可以更利落一点，让dfs直接担任寻找答案的任务：

Python3 点击展开代码

22 lines 展开代码

def validPath(self, n: int, edges: list[list[int]], source: int, destination: int) -> bool:
    # 建立邻接表
    graph = [[] for _ in range(n)]
    for edge in edges:
        graph[edge[0]].append(edge[1])
        graph[edge[1]].append(edge[0])

    # 写dfs函数
    visited = set()
    def dfs(node)->bool:
        if node == destination:
            return True
        if node in visited:
            return False
        visited.add(node)
        for nxt in graph[node]:
            # 只要有一个dfs通了即可
            if dfs(nxt):
                return True
        # 兜底
        return False
    return dfs(source)

所有路径搜索#

LC797 - 所有可能的路径#

这一题是一道标准的DAG路径所有路径搜索，我们维持一个path，如果到达了终点就将path加入答案。记得path要回溯即可：

Python3 点击展开代码

15 lines 展开代码

def allPathsSourceTarget(self, graph: list[list[int]]) -> list[list[int]]:
    # 本题已给邻接表
    path = []
    path.append(0)
    ans = []
    n = len(graph)
    def dfs(node):
        if node ==  n-1:
            ans.append(path[:])
        for nxt in graph[node]:
            path.append(nxt)
            dfs(nxt)
            path.pop()
    dfs(0)
    return ans

这一版可以写的更优雅一些，每次dfs开始就path加入node，然后再进入递归退出判断。

Python3 点击展开代码

13 lines 展开代码

    ans = []
    path = []
    target = len(graph) - 1
    def dfs(node):
        path.append(node)
        if node == target:
            ans.append(path[:])
        else:
            for nxt in graph[node]:
                dfs(nxt)
        path.pop()
    dfs(0)
    return ans

LC113 - 路径总和 II#

本题只要求根节点到叶子结点的总和，直接在dfs中维持一个total，判断到叶子的时候是否等于target就行。（注意到空节点不一定是到了叶子节点后，所以要特判叶子节点）

Python3 点击展开代码

22 lines 展开代码

def pathSum(self, root: TreeNode, targetSum: int) -> list[list[int]]:
    if not root:
        return []
    ans = []
    path = []
    def dfs(node,total):
        if not node:
            return
        
        path.append(node.val)
        total += node.val

        if not node.left and not node.right and total == targetSum:
            ans.append(path[:])
            # 这里不可以return！因为这种写法这里return就会弹不出当前元素
            # return
        else:
            dfs(node.left,total)
            dfs(node.right,total)
        path.pop()
    dfs(root,0)
    return ans

如果在LC上提交这个解法，可以发现非常慢，其实对于这类还有一个小优化，那就是不要传累加和了，直接传剩余和，这样就是100%了：

Python3 点击展开代码

21 lines 展开代码

def pathSum(self, root: TreeNode, targetSum: int) -> list[list[int]]:
    ans = []
    path = []

    def dfs(node, remain):
        if not node:
            return

        path.append(node.val)
        remain -= node.val

        if not node.left and not node.right and remain == 0:
            ans.append(path[:])
        else:
            dfs(node.left, remain)
            dfs(node.right, remain)

        path.pop()

    dfs(root, targetSum)
    return ans

LC257 - 二叉树的所有路径#

简单题，直接dfs到叶子节点就行。

Python3 点击展开代码

21 lines 展开代码

class TreeNode:
    def __init__(self, val = 0, left = None, right = None):
        self.val = val 
        self.left = left
        self.right = right

def binaryTreePaths(self, root: TreeNode) -> list[str]:
    path = []
    ans = []
    def dfs(node):
        if not node:
            return
        path.append(str(node.val))
        if not node.left and not node.right:
            ans.append("->".join(path))
        else:
            dfs(node.left)
            dfs(node.right)
        path.pop()
    dfs(root)
    return ans

DFS 常见模板#

图 DFS：

Python3 点击展开代码

6 lines 展开代码

def dfs(node):
    if node in visited:
        return
    visited.add(node)
    for nxt in graph[node]:
        dfs(nxt)

回溯 DFS：

Python3 点击展开代码

11 lines 展开代码

def dfs(state):
    if 满足答案条件:
        ans.append(path[:])
        return

    for choice in choices:
        if 不合法:
            continue
        path.append(choice)
        dfs(next_state)
        path.pop()

BFS 搜索：一层一层扩散#

BFS 的核心思想#

BFS 的核心是"从起点一层一层向外扩散"。队列中的节点按照距离起点由近到远的顺序被处理，所以在无权图中，第一次到达某个状态时就是最短距离。

BFS 为什么能求最短路#

因为 BFS 每一轮只走一步，先处理距离为 k 的所有状态，再处理距离为 k + 1 的状态。如果边权都相同，第一次遇到终点时，不可能还有更短路径没被处理。

BFS 中的队列和层数#

常见层数写法是：

Python3 点击展开代码

6 lines 展开代码

step = 0
while q:
    for _ in range(len(q)):
        cur = q.popleft()
        ...
    step += 1

也可以把距离和节点一起入队，比如 q.append((node, dist))。

BFS 中的 visited#

BFS 的 visited 最好在入队时就标记，而不是出队时再标记。这样可以避免同一个状态被多个父节点重复加入队列。

无权图最短路#

LC752 - 打开转盘锁#

简单来说，一次操作可以有8种不同的状态转移，询问能不能到达最终状态。但是，这题需要返回最小旋转次数，所以一定是需要bfs一层一层往外数。

Python3 点击展开代码

42 lines 展开代码

from collections import deque

def openLock(self, deadends: list[str], target: str) -> int:
    def update(state: str) -> list[str]:
        res = []
        chars = list(state)
        for i in range(4):
            old = chars[i]

            chars[i] = str((int(old) + 1) % 10)
            res.append("".join(chars))

            chars[i] = str((int(old) + 9) % 10)
            res.append("".join(chars))

            chars[i] = old
        return res

    visited = set(deadends)
    if "0000" in visited:
        return -1
    if target == "0000":
        return 0

    q = deque(["0000"])
    visited.add("0000")
    step = 0

    while q:
        for _ in range(len(q)):
            cur = q.popleft()
            if cur == target:
                return step

            for nxt in update(cur):
                if nxt not in visited:
                    visited.add(nxt)
                    q.append(nxt)

        step += 1

    return -1

注意一下层数统计和去重等操作。

LC773 - 滑动谜题#

同样是问多少次，使用广搜，不过注意这里的状态转移可以转化成一维来做。注意去重要tuple。

Python3 点击展开代码

50 lines 展开代码

from collections import deque


def slidingPuzzle(self, board: list[list[int]]) -> int:
    flat = [x for row in board for x in row]
    target = [1, 2, 3, 4, 5, 0]

    def update(state: list[int]) -> list[list[int]]:
        zero_idx = state.index(0)

        match zero_idx:
            case 0:
                nxts = [1, 3]
            case 1:
                nxts = [0, 2, 4]
            case 2:
                nxts = [1, 5]
            case 3:
                nxts = [0, 4]
            case 4:
                nxts = [1, 3, 5]
            case 5:
                nxts = [2, 4]

        res = []
        for nxt in nxts:
            new_state = state[:]
            new_state[zero_idx], new_state[nxt] = new_state[nxt], new_state[zero_idx]
            res.append(new_state)
        return res

    q = deque([flat])
    visited = {tuple(flat)}
    step = 0

    while q:
        for _ in range(len(q)):
            cur = q.popleft()
            if cur == target:
                return step

            for nxt in update(cur):
                nxt_tuple = tuple(nxt)
                if nxt_tuple not in visited:
                    visited.add(nxt_tuple)
                    q.append(nxt)

        step += 1

    return -1

LC1091 - 二进制矩阵中的最短路径#

需要找畅通路径的长度，所以用 BFS。其实就是一道起点到终点的最短路题目，先定义好 8 个方向即可。注意 visited 更新、判断位置等，多练。

Python3 点击展开代码

25 lines 展开代码

from collections import deque

def shortestPathBinaryMatrix(self, grid: list[list[int]]) -> int:
    n = len(grid)
    if not grid or grid[0][0] == 1 or grid[n-1][n-1] == 1:
        return -1
    steps = [(1,0),(1,1),(1,-1),(-1,0),(-1,1),(-1,-1),(0,-1),(0,1)]
    q = deque([(0,0)])
    visited = {(0,0)}
    # 途径的单元格总数，所以不包括起点
    count = 1
    while q:
        sz = len(q)
        for _ in range(sz):
            x,y = q.popleft()
            if (x,y) == (n-1,n-1):
                return count
            for dx,dy in steps:
                nx = x + dx
                ny = y + dy
                if 0<=nx<n and 0<=ny<n and grid[nx][ny] == 0 and (nx,ny) not in visited:
                    visited.add((nx,ny))
                    q.append((nx,ny))
        count += 1
    return -1

LC1926 - 迷宫中离入口最近的出口#

最近的出口，还是最短路径，直接一个bfs。

Python3 点击展开代码

32 lines 展开代码

from collections import deque

def nearestExit(self, maze: list[list[str]], entrance: list[int]) -> int:
    if not maze:
        return -1
    directions = [(1,0),(-1,0),(0,-1),(0,1)]
    m = len(maze)
    n = len(maze[0])
    visited = set()
    for x in range(m):
        for y in range(n):
            if maze[x][y] == "+":
                visited.add((x,y))
    # 开始bfs，只要移动到变边界就成功
    step = 0
    q = deque([(entrance[0],entrance[1])])
    visited.add((entrance[0],entrance[1]))
    while q:
        sz = len(q)
        for _ in range(sz):
            x, y = q.popleft()
            # 注意题目明确说起点不能作为出口
            if step > 0 and (x == 0 or x == m-1 or y == 0 or y == n-1):
                return step
            for dx, dy in directions:
                nx = x + dx
                ny = y + dy
                if 0<=nx<m and 0<=ny<n and (nx,ny) not in visited:
                    visited.add((nx,ny))
                    q.append((nx,ny))
        step += 1
    return -1

当然，既然是要遍历，其实可以不用先把墙放进visited，而是在入队判断时候加，像这样：

Python3 点击展开代码

29 lines 展开代码

from collections import deque

def nearestExit(self, maze: list[list[str]], entrance: list[int]) -> int:
    if not maze:
        return -1

    m, n = len(maze), len(maze[0])
    directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

    q = deque([(entrance[0], entrance[1])])
    visited = {(entrance[0], entrance[1])}
    step = 0

    while q:
        for _ in range(len(q)):
            x, y = q.popleft()

            if step > 0 and (x == 0 or x == m - 1 or y == 0 or y == n - 1):
                return step

            for dx, dy in directions:
                nx, ny = x + dx, y + dy
                if 0 <= nx < m and 0 <= ny < n and maze[nx][ny] == '.' and (nx, ny) not in visited:
                    visited.add((nx, ny))
                    q.append((nx, ny))

        step += 1

    return -1

速度上会快点。

多源 BFS#

LC994 - 腐烂的橘子#

这一题注意维持一个fresh，这样多源bfs之后才知道是否感染完毕。我们准备一个感染队列，先遍历一遍将感染坐标入队，然后开始一层一层感染。

Python3 点击展开代码

28 lines 展开代码

from collections import deque

def orangesRotting(self, grid: list[list[int]]) -> int:
    m = len(grid)
    n = len(grid[0])
    q = deque()
    fresh = 0
    for x in range(m):
        for y in range(n):
            if grid[x][y] == 2:
                q.append((x,y))
            elif grid[x][y] == 1:
                fresh += 1
    # 开始 BFS，检查四个方向有没有新鲜橘子
    directions = [(1,0),(-1,0),(0,1),(0,-1)]
    step = 0
    while q and fresh>0:
        for _ in range(len(q)):
            x,y = q.popleft()
            for dx, dy in directions:
                nx = x + dx
                ny = y + dy
                if 0<=nx<m and 0<=ny<n and grid[nx][ny] == 1:
                    grid[nx][ny] = 2
                    q.append((nx,ny))
                    fresh -= 1
        step += 1
    return step if fresh == 0 else -1

我们可以观察发现，这一题和上一题的返回时机不一样。这是因为，上一题找路径，到达某个路径之后，答案就已经出来了，但是感染橘子就算循环中干扰上了，也还在这一分钟内，要等待step+=1。

LC542 - 01 矩阵#

我们定义一个bfs函数，返回step，然后对每一个点调用，这样就能得到新矩阵了。

Python3 点击展开代码

32 lines 展开代码

from collections import deque

def updateMatrix(self, mat: list[list[int]]) -> list[list[int]]:
    m = len(mat)
    n = len(mat[0])
    # 负责输出周围最近的0的距离
    def bfs(x,y)->int:
        directions = [(-1,0),(1,0),(0,1),(0,-1)]
        q = deque([(x,y)])
        step = 0
        visited = set()
        visited.add((x,y))
        while q:
            for _ in range(len(q)):
                x,y = q.popleft()
                if mat[x][y] == 0:
                    return step
                for dx,dy in directions:
                    nx = x + dx
                    ny = y + dy
                    if 0<=nx<m and 0<=ny<n and (nx,ny) not in visited:
                        visited.add((nx,ny))
                        q.append((nx,ny))
            step += 1
        return -1
    
    result = [row[:] for row in mat]

    for i in range(m):
        for j in range(n):
            result[i][j] = bfs(i,j)
    return result

从思路上来说没问题，但是这一题这样写铁超时的，因为我们要每次对一个点做一个bfs。多源bfs的要点是，我们将需要bfs的点先一起入队，然后一起处理。所以，我们应该写成这样：

Python3 点击展开代码

26 lines 展开代码

from collections import deque

def updateMatrix(self, mat: list[list[int]]) -> list[list[int]]:
    m = len(mat)
    n = len(mat[0])
    q = deque()
    dist = [[-1]*n for _ in range(m)]
    for i in range(m):
        for j in range(n):
            if mat[i][j] == 0:
                dist[i][j] = 0
                q.append((i,j))

    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]

    # 多源bfs
    while q:
        x,y = q.popleft()
        for dx,dy in directions:
            nx,ny = x + dx, y + dy
            # dist兼用visited
            if 0<=nx<m and 0<=ny<n and dist[nx][ny] == -1:
                # 向外扩散
                dist[nx][ny] = dist[x][y] + 1
                q.append((nx,ny))
    return dist

LC286 - 墙与门#

这一题和上一题 LC542 - 01 矩阵 几乎是同一种味道，都是典型的多源 BFS。

题目大意如下：

给定一个 m x n 的二维网格 rooms，其中每个位置有三种可能的值：

-1 表示墙或者障碍物
0 表示一扇门
INF 表示一个空房间，这里的 INF = 2147483647

要求你把每个空房间替换成它到最近门的距离。如果无法走到任何门，那么这个位置保持 INF 不变。

例如：

1
输入：
2
INF  -1   0  INF
3
INF INF INF  -1
4
INF  -1 INF  -1
5
  0  -1 INF INF

运行之后应变成：

1
  3  -1   0   1
2
  2   2   1  -1
3
  1  -1   2  -1
4
  0  -1   3   4

这题如果朴素去想，很容易写成"对每个空房间单独做一次 BFS 去找最近的门"，但那样复杂度会很高。更好的方式是：

把所有门 0 一起入队
同时向外扩散
第一次更新到某个空房间时，这个距离就是它到最近门的最短距离

Python3 点击展开代码

24 lines 展开代码

from collections import deque

def wallsAndGates(self, rooms: list[list[int]]) -> None:
    if not rooms or not rooms[0]:
        return

    INF = 2147483647
    m, n = len(rooms), len(rooms[0])
    q = deque()

    for i in range(m):
        for j in range(n):
            if rooms[i][j] == 0:
                q.append((i, j))

    directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

    while q:
        x, y = q.popleft()
        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            if 0 <= nx < m and 0 <= ny < n and rooms[nx][ny] == INF:
                rooms[nx][ny] = rooms[x][y] + 1
                q.append((nx, ny))

双向 BFS#

LC127 - 单词接龙#

字典 wordList 中从单词 beginWord 到 endWord 的转换序列是一个按下述规格形成的序列 beginWord -> s1 -> s2 -> … -> sk：

每一对相邻的单词只差一个字母。
对于 1 <= i <= k 时，每个 si 都在 wordList 中。注意， beginWord 不需要在 wordList 中。
sk == endWord

给你两个单词 beginWord 和 endWord 和一个字典 wordList ，返回从 beginWord 到 endWord 的最短转换序列中的单词数目。如果不存在这样的转换序列，返回 0 。

本题也是求到终点的路径长度，当相差一个字母的时候可以转移，我们通过辅助函数来判断能不能转移。

但是，如果这一题从一头开始搜，因为一个单词可以改26个字母，如果只从一路搜，路数会膨胀得很快。所以我们从两边一起往中间搜，只要遇到了，就存在。

Python3 点击展开代码

43 lines 展开代码

def ladderLength(self, beginWord: str, endWord: str, wordList: list[str]) -> int:
    word_set = set(wordList)
    if endWord not in word_set:
        return 0

    begin_set = {beginWord}
    end_set = {endWord}
    visited = {beginWord, endWord}
    step = 1

    while begin_set and end_set:
        # 始终从更小的一侧扩展，减少分支数
        if len(begin_set) > len(end_set):
            begin_set, end_set = end_set, begin_set

        next_level = set()

        for word in begin_set:
            word_chars = list(word)

            for i in range(len(word_chars)):
                old = word_chars[i]

                for ch in 'abcdefghijklmnopqrstuvwxyz':
                    if ch == old:
                        continue

                    word_chars[i] = ch
                    new_word = ''.join(word_chars)

                    if new_word in end_set:
                        return step + 1

                    if new_word in word_set and new_word not in visited:
                        visited.add(new_word)
                        next_level.add(new_word)

                word_chars[i] = old

        begin_set = next_level
        step += 1

    return 0

BFS 常见模板#

单源 BFS：

Python3 点击展开代码

16 lines 展开代码

from collections import deque

q = deque([start])
visited = {start}
step = 0

while q:
    for _ in range(len(q)):
        cur = q.popleft()
        if cur == target:
            return step
        for nxt in get_next(cur):
            if nxt not in visited:
                visited.add(nxt)
                q.append(nxt)
    step += 1

多源 BFS 的差别是：先把所有源点一起入队，并全部标记为已访问。

网格搜索：二维数组上的 DFS 和 BFS#

网格搜索的核心理解#

网格搜索可以看成图搜索：每个格子是节点，四个方向或八个方向是边。关键是先统一方向数组，再把越界、障碍、访问过这些条件写清楚。

网格 DFS 模板#

Python3 点击展开代码

10 lines 展开代码

directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

def dfs(i, j):
    if not (0 <= i < m and 0 <= j < n):
        return
    if is_blocked(i, j):
        return
    grid[i][j] = VISITED
    for dx, dy in directions:
        dfs(i + dx, j + dy)

网格 BFS 模板#

Python3 点击展开代码

13 lines 展开代码

from collections import deque

directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
q = deque([(start_x, start_y)])
visited = {(start_x, start_y)}

while q:
    x, y = q.popleft()
    for dx, dy in directions:
        nx, ny = x + dx, y + dy
        if 0 <= nx < m and 0 <= ny < n and (nx, ny) not in visited:
            visited.add((nx, ny))
            q.append((nx, ny))

岛屿类问题#

LC200 - 岛屿数量#

岛屿数量是经典的多源dfs，每次dfs的时候我们将相邻的1全部变为0，二重循环进行dfs，最后统计dfs的次数即可。注意一下dfs的退出条件即可。

Python3 点击展开代码

19 lines 展开代码

def numIslands(self, grid: list[list[str]]) -> int:
    m = len(grid)
    n = len(grid[0])
    def dfs(i,j):
        if not 0<=i<m or not 0<=j<n or grid[i][j] == '0':
            return
        grid[i][j] = '0'
        dfs(i+1,j)
        dfs(i-1,j)
        dfs(i,j+1)
        dfs(i,j-1)

    count = 0
    for i in range(m):
        for j in range(n):
            if grid[i][j] == '1':
                dfs(i,j)
                count += 1
    return count

LC695 - 岛屿的最大面积#

岛屿的最大面积，我们直接让dfs返回这次遍历的面积即可，也就是返回的时候加上方向的dfs。

Python3 点击展开代码

16 lines 展开代码

def maxAreaOfIsland(self, grid: list[list[int]]) -> int:
    m = len(grid)
    n = len(grid[0])
    def dfs(i,j):
        if not 0<=i<m or not 0<=j<n or grid[i][j] == 0:
            return 0
        grid[i][j] = 0
        return 1+dfs(i+1,j)+dfs(i-1,j)+dfs(i,j+1)+dfs(i,j-1)

    max_S = 0
    for i in range(m):
        for j in range(n):
            if grid[i][j] == 1:
                S = dfs(i,j)
                max_S = max(S,max_S)
    return max_S

LC1254 - 统计封闭岛屿的数目#

这一题的思路是，我们先遍历边界，与边界相邻的大陆必不可能是被包围的岛，所以直接淹掉。然后，就变成了岛屿数目统计，在水中间的都是被包围的。

Python3 点击展开代码

31 lines 展开代码

def closedIsland(self, grid: list[list[int]]) -> int:
        m = len(grid)
        n = len(grid[0])
        def dfs(i,j):
            if not 0<=i<m or not 0<=j<n or grid[i][j] == 1:
                return
            grid[i][j] = 1
            dfs(i+1,j)
            dfs(i-1,j)
            dfs(i,j+1)
            dfs(i,j-1)

        # 加一个淹没边界
        for i in range(m):
            if grid[i][0] == 0:
                dfs(i,0)
            if grid[i][n-1] == 0:
                dfs(i,n-1)
        for j in range(n):
            if grid[0][j] == 0:
                dfs(0,j)
            if grid[m-1][j] == 0:
                dfs(m-1,j)

        count = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 0:
                    dfs(i,j)
                    count += 1
        return count

LC1020 - 飞地的数量#

也是边界淹没，然后统计内部面积就行。

Python3 点击展开代码

23 lines 展开代码

def numEnclaves(self, grid: list[list[int]]) -> int:
        m = len(grid)
        n = len(grid[0])
        def dfs(i,j):
            if not 0<=i<m or not 0<=j<n or grid[i][j] == 0:
                return 0
            grid[i][j] = 0
            return 1+dfs(i+1,j)+dfs(i-1,j)+dfs(i,j+1)+dfs(i,j-1)

        # 加一个淹没边界
        for i in range(m):
            dfs(i,0)
            dfs(i,n-1)
        for j in range(n):
            dfs(0,j)
            dfs(m-1,j)

        total = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1:
                    total += dfs(i,j)     
        return total

LC463 - 岛屿的周长#

这一题让dfs返回周长贡献，有三种情况：

某方向越界，说明是外边界，贡献为1
某方向临水，说明露出来，贡献也是1
某方向贴着陆地，贡献就是0了

Python3 点击展开代码

18 lines 展开代码

def islandPerimeter(self, grid: list[list[int]]) -> int:
        m = len(grid)
        n = len(grid[0])
        visited = set()
        def dfs(i,j):
            if not 0<=i<m or not 0<=j<n or grid[i][j] == 0:
                return 1
            if (i,j) in visited:
                return 0
            visited.add((i,j))
            return dfs(i+1,j)+dfs(i-1,j)+dfs(i,j+1)+dfs(i,j-1)

        # 只有一块岛屿
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1:
                    return dfs(i,j) 
        return 0

注意这一题不能将陆地简单变成水，否则会影响到周长计算，所以我们需要额外的visited统计这里有没有算过，防止回头。

边界反向搜索#

LC130 - 被围绕的区域#

这一题就是将被X围绕的所有O变成X。我们可以先看边界来dfs，将O先变成#，然后将剩下的O全变成X，再将#变成O。

Python3 点击展开代码

31 lines 展开代码

def solve(self, board: list[list[str]]) -> None:
    if not board or not board[0]:
        return

    m, n = len(board), len(board[0])

    def dfs(i, j):
        if not (0 <= i < m and 0 <= j < n) or board[i][j] != 'O':
            return

        board[i][j] = '#'

        dfs(i + 1, j)
        dfs(i - 1, j)
        dfs(i, j + 1)
        dfs(i, j - 1)

    for i in range(m):
        dfs(i, 0)
        dfs(i, n - 1)

    for j in range(n):
        dfs(0, j)
        dfs(m - 1, j)

    for i in range(m):
        for j in range(n):
            if board[i][j] == 'O':
                board[i][j] = 'X'
            elif board[i][j] == '#':
                board[i][j] = 'O'

LC417 - 太平洋大西洋水流问题#

如果每个格子 DFS 两次来判断会比较麻烦，我们可以分别从太平洋和大西洋边界区 DFS，然后每次往高处爬，将能够到的位置全都存入各自的 set 中，最后判断同时在两个 set 中的位置。

Python3 点击展开代码

36 lines 展开代码

def pacificAtlantic(self, heights: list[list[int]]) -> list[list[int]]:
    m, n = len(heights), len(heights[0])
    
    pacific = set()
    atlantic = set()

    def dfs(i, j, visited, prev_height):
        if not (0 <= i < m and 0 <= j < n):
            return
        if (i, j) in visited:
            return
        if heights[i][j] < prev_height:
            return

        visited.add((i, j))

        dfs(i + 1, j, visited, heights[i][j])
        dfs(i - 1, j, visited, heights[i][j])
        dfs(i, j + 1, visited, heights[i][j])
        dfs(i, j - 1, visited, heights[i][j])

    for i in range(m):
        dfs(i, 0, pacific, heights[i][0])
        dfs(i, n - 1, atlantic, heights[i][n - 1])

    for j in range(n):
        dfs(0, j, pacific, heights[0][j])
        dfs(m - 1, j, atlantic, heights[m - 1][j])

    ans = []
    for i in range(m):
        for j in range(n):
            if (i, j) in pacific and (i, j) in atlantic:
                ans.append([i, j])

    return ans

单词与路径搜索#

LC79 - 单词搜索#

二重循环枚举每个格子作为起点，如果该格子等于单词首字母，就从这里开始 DFS。DFS 中用 pos 表示当前匹配到 word[pos]，用 visited 防止当前路径中重复使用同一个格子。若 pos == len(word)，说明整个单词匹配成功，返回 True。每次递归结束后需要回溯，将当前格子从 visited 中移除；如果所有起点都无法匹配，则返回 False。

Python3 点击展开代码

36 lines 展开代码

def exist(self, board: list[list[str]], word: str) -> bool:
    m, n = len(board), len(board[0])
    visited = set()

    def dfs(i, j, pos):
        if pos == len(word):
            return True

        if not (0 <= i < m and 0 <= j < n):
            return False

        if (i, j) in visited:
            return False

        if board[i][j] != word[pos]:
            return False

        visited.add((i, j))

        found = (
            dfs(i + 1, j, pos + 1)
            or dfs(i - 1, j, pos + 1)
            or dfs(i, j + 1, pos + 1)
            or dfs(i, j - 1, pos + 1)
        )

        visited.remove((i, j))

        return found

    for i in range(m):
        for j in range(n):
            if board[i][j] == word[0] and dfs(i, j, 0):
                return True

    return False

注意这里是路径级别的visited而不是全局，所以每个dfs中会进行回溯。

LC212 - 单词搜索 II#

如果这一题按照n次单词搜索来做就会超时，因为当words很多的时候，重复搜索会非常严重。这一题实际上是标准的Trie字典树+DFS回溯。

Trie树是一种用空间换时间的结构，如果你还记得，hot100中有一题就是让构建Trie树。构建好Trie树之后，这一题就是从每个点开始往下搜，搜到了就append答案。

Python3 点击展开代码

61 lines 展开代码

def findWords(self, board: list[list[str]], words: list[str]) -> list[str]:
    class TrieNode:
        def __init__(self):
            self.children = {}
            self.word = None
        
    class Trie:
        def __init__(self):
            self.root = TrieNode()

        def insert(self,word:str):
            node = self.root
            for ch in word:
                if ch not in node.children:
                    node.children[ch] = TrieNode()
                node = node.children[ch]
            node.word = word

    # 初始化Trie树
    T = Trie()
    for word in words:
        T.insert(word)
    
    # 开始检查，从i、j开始，能不能找到单词
    m = len(board)
    n = len(board[0])

    ans = []

    def dfs(i, j, node):
        if not (0 <= i < m and 0 <= j < n):
            return

        ch = board[i][j]

        # 遍历过或者不在后续
        if ch == "#" or ch not in node.children:
            return

        nxt = node.children[ch]
        # 如果找到
        if nxt.word is not None:
            ans.append(nxt.word)
            nxt.word = None

        # 防止回头
        board[i][j] = "#"

        dfs(i + 1, j, nxt)
        dfs(i - 1, j, nxt)
        dfs(i, j + 1, nxt)
        dfs(i, j - 1, nxt)

        # 路径级回溯
        board[i][j] = ch

    for i in range(m):
        for j in range(n):
            dfs(i, j, T.root)

    return ans

网格搜索常见坑点#

grid 里到底是字符串 '1' 还是整数 1，要看题目类型。
DFS 能不能原地修改，取决于修改后会不会影响后续判断。
BFS 的 visited 尽量入队时标记。
求最短路优先 BFS，求连通块数量/面积优先 DFS。
边界反向搜索常用于"被边界影响的区域不算答案"的题。

回溯搜索：枚举所有选择#

回溯的核心思想#

回溯就是 DFS 枚举选择，并在递归返回后撤销选择。它适合解决"所有方案""所有组合""所有排列""所有切割方式"这类题。

回溯和 DFS 的关系#

回溯是 DFS 的一种特殊写法。普通 DFS 只关心能不能走到；回溯还要维护路径，并在离开当前选择时恢复现场。

path、choice、used 的含义#

path 表示当前已经构造出的方案，choice 表示这一层可选的候选项，used 或 visited 表示哪些元素在当前路径中已经被使用。

子集问题#

LC78 - 子集#

经典子集问题，默写级别。两种递归，要么递归 i 选不选，要么递归从 start 开始往下枚举选谁，首先是 start 模板：

Python3 点击展开代码

11 lines 展开代码

def subsets(self, nums: list[int]) -> list[list[int]]:
    path = []
    ans = []
    def dfs(start:int):
        ans.append(path[:])
        for i in range(start,len(nums)):
            path.append(nums[i])
            dfs(i+1)
            path.pop()
    dfs(0)
    return ans

这里的 for 循环负责枚举"下一个要选的元素"；而"不再继续选"的情况，由进入 DFS 后立刻 ans.append(path[:]) 表示。所以不用你手动维护不选。

我们再来看看位置的思路，更加自然，但是通用性降低，也就是直接遍历候选，看看选不选。

Python3 点击展开代码

13 lines 展开代码

def subsets(self, nums: list[int]) -> list[list[int]]:
    path = []
    ans = []
    def dfs(i):
        if i == len(nums):
            ans.append(path[:])
            return
        path.append(nums[i])
        dfs(i+1)
        path.pop()
        dfs(i+1)
    dfs(0)
    return ans

LC90 - 子集 II#

先sort一下，然后重复元素跳过就行。

Python3 点击展开代码

15 lines 展开代码

def subsetsWithDup(self, nums: list[int]) -> list[list[int]]:
    nums.sort()
    ans = []
    path = []
    def dfs(start):
        ans.append(path[:])
        # 跳过重复元素
        for i in range(start,len(nums)):
            if i>start and nums[i-1] == nums[i]:
                continue
            path.append(nums[i])
            dfs(i+1)
            path.pop()
    dfs(0)
    return ans

组合问题#

LC77 - 组合#

组合问题，要求返回范围 [1, n] 中所有可能的 k 个数的组合，不能复选。其实判断加入ans的条件就是 len(path) == k，其余的和子集差不多。

Python3 点击展开代码

15 lines 展开代码

from typing import List

def combine(self, n: int, k: int) -> List[List[int]]:
    ans = []
    path = []
    def dfs(start):
        if len(path) == k:
            ans.append(path[:])
            return
        for i in range(start,n+1):
            path.append(i)
            dfs(i+1)
            path.pop()
    dfs(1)
    return ans

LC39 - 组合总和#

找出数字和为目标数target的组合，而且可以重复选，而且candidates无重复元素。

Python3 点击展开代码

18 lines 展开代码

from typing import List

def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
    ans = []
    path = []
    def dfs(start,target):
        if target<0:
            return
        if target == 0:
            ans.append(path[:])
            return
        for i in range(start,len(candidates)):
            path.append(candidates[i])
            # 可复选，不用i+1
            dfs(i,target - candidates[i])
            path.pop()
    dfs(0,target)
    return ans

LC40 - 组合总和 II#

与上一题的区别在于每个数字只能使用一次+组合不允许重复，且candidates中可有重复元素。

Python3 点击展开代码

21 lines 展开代码

from typing import List

def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
    candidates.sort()
    ans = []
    path = []
    def dfs(start,target):
        if target<0:
            return
        if target == 0:
            ans.append(path[:])
            return
        
        for i in range(start,len(candidates)):
            if i>start and candidates[i-1] == candidates[i]:
                continue
            path.append(candidates[i])
            dfs(i+1,target-candidates[i])
            path.pop()
    dfs(0,target)
    return ans

LC216 - 组合总和 III#

找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：

只使用数字1到9
每个数字最多使用一次

且不能重复组合。其实就是上一题的简化版，候选变成了1-9。

Python3 点击展开代码

17 lines 展开代码

from typing import List

def combinationSum3(self, k: int, n: int) -> List[List[int]]:
    ans = []
    path = []
    def dfs(start,target):
        if target < 0:
            return
        if target == 0 and len(path) == k:
            ans.append(path[:])
            return
        for i in range(start,10):
            path.append(i)
            dfs(i+1,target-i)
            path.pop()
    dfs(1,n)
    return ans

排列问题#

LC46 - 全排列#

排列问题中，我们每次都要重头开始数，因为可能后面排在前面。因此，我们还要维护一个数组，来表示对应下标有没有被使用过。

Python3 点击展开代码

21 lines 展开代码

from typing import List

def permute(self, nums: List[int]) -> List[List[int]]:
    n = len(nums)
    seen = [False]*n
    path = []
    ans = []
    def dfs():
        if len(path) == n:
            ans.append(path[:])
            return
        for i in range(n):
            if seen[i]:
                continue
            seen[i] = True
            path.append(nums[i])
            dfs()
            path.pop()
            seen[i] = False
    dfs()
    return ans

LC47 - 全排列 II#

给定一个可包含重复数字的序列 nums ，按任意顺序返回所有不重复的全排列。

其实跟刚才是一样的，就是多了个重复元素，排序后跳过。

Python3 点击展开代码

25 lines 展开代码

from typing import List

def permuteUnique(self, nums: List[int]) -> List[List[int]]:
    nums.sort()
    n = len(nums)
    seen = [False]*n
    path = []
    ans = []
    def dfs():
        if len(path) == n:
            ans.append(path[:])
            return
        for i in range(n):
            if seen[i]:
                continue
            # 多了一个判断，如果之前没用，现在也不准用，也就是说不允许有顺序区分
            if i>0 and nums[i] == nums[i-1] and not seen[i-1]:
                continue
            seen[i] = True
            path.append(nums[i])
            dfs()
            path.pop()
            seen[i] = False
    dfs()
    return ans

切割问题#

LC131 - 分割回文串#

一维分割问题其实就是每次找到一种方案之后再递归下一个位置分割，直到分割完毕保存答案。

Python3 点击展开代码

27 lines 展开代码

from typing import List

def partition(self, s: str) -> List[List[str]]:
    def palindrome(string:str):
        i, j = 0, len(string)-1
        while i<j:
            if string[i]!=string[j]:
                return False
            i += 1
            j -= 1
        return True
    
    ans = []
    path = []

    def dfs(start):
        if start == len(s):
            ans.append(path[:])
            return
        for i in range(start,len(s)):
            curr = s[start:i+1]
            if palindrome(curr):
                path.append(curr)
                dfs(i+1)
                path.pop()
    dfs(0)
    return ans

LC93 - 复原 IP 地址#

跟上一题类似的划分类问题，判断每个划分合不合理，出了额外判断最后是不是被分为了4段之外，还有每段不超过3位、前导0等，总体难在各种情况都考虑到。

Python3 点击展开代码

27 lines 展开代码

from typing import List

def restoreIpAddresses(self, s: str) -> List[str]:
    def isValid(string:str):
        if string[0] == '0' and len(string)>1:
            return False
        num = int(string)
        return 0<=num<=255
    
    path = []
    ans = []
    def dfs(start):
        if len(path)>4:
            return
        if start == len(s):
            if len(path) == 4:
                ans.append(".".join(path))
            return
        # 这里要限制最多三位
        for i in range(start,min(start+3,len(s))):
            curr = s[start:i+1]
            if isValid(curr):
                path.append(curr)
                dfs(i+1)
                path.pop()
    dfs(0)
    return ans

棋盘搜索#

LC51 - N 皇后#

N皇后需要用集合存储一下行、列、主对角、副对角是否被用了。其中主对角和副对角就是用坐标的关系，主对角作差定值，副对角求和定值。

Python3 点击展开代码

24 lines 展开代码

from typing import List

def solveNQueens(self, n: int) -> List[List[str]]:
    col, diag1, diag2 = set(), set(), set()
    # 由于每一行最多放一个，用dfs(i)表示放第i行
    ans = []
    grid = [['.']*n for _ in range(n)]
    def dfs(i):
        if i == n:
            ans.append(["".join(row) for row in grid])
            return
        for j in range(n):
            if j not in col and i+j not in diag1 and i-j not in diag2:
                grid[i][j] = 'Q'
                col.add(j)
                diag1.add(i+j)
                diag2.add(i-j)
                dfs(i+1)
                grid[i][j] = '.'
                col.remove(j)
                diag1.remove(i+j)
                diag2.remove(i-j)
    dfs(0)
    return ans

LC52 - N 皇后 II#

基本是N皇后的简化版，只要统计数目。

Python3 点击展开代码

22 lines 展开代码

from typing import List

def totalNQueens(self, n: int) -> int:
    col, diag1, diag2 = set(), set(), set()
    # 由于每一行最多放一个，用dfs(i)表示放第i行
    count = 0
    def dfs(i):
        nonlocal count
        if i == n:
            count += 1
            return
        for j in range(n):
            if j not in col and i+j not in diag1 and i-j not in diag2:
                col.add(j)
                diag1.add(i+j)
                diag2.add(i-j)
                dfs(i+1)
                col.remove(j)
                diag1.remove(i+j)
                diag2.remove(i-j)
    dfs(0)
    return count

LC37 - 解数独#

这里有三个要求，首先是行集合，然后是列结合，最后还有一个3x3box内的集合，这个我们用取余实现找到在第几个小方格内。

然后，我们是通过找出所有空位，然后用dfs去一个一个填，看看能不能找到解决问题的答案。

Python3 点击展开代码

49 lines 展开代码

def solveSudoku(self, board: list[list[str]]) -> None:
    rows = [set() for _ in range(9)]
    cols = [set() for _ in range(9)]
    boxes = [set() for _ in range(9)]
    # 先找出所有空位，然后dfs去填
    spaces = []

    for i in range(9):
        for j in range(9):
            if board[i][j] == ".":
                spaces.append((i, j))
            else:
                num = board[i][j]
                rows[i].add(num)
                cols[j].add(num)
                # 还有3x3也要去重合
                boxes[(i // 3) * 3 + j // 3].add(num)

    def dfs(idx: int) -> bool:
        if idx == len(spaces):
            return True

        i, j = spaces[idx]
        box_idx = (i // 3) * 3 + j // 3

        for num in map(str, range(1, 10)):
            if num in rows[i]:
                continue
            if num in cols[j]:
                continue
            if num in boxes[box_idx]:
                continue

            board[i][j] = num
            rows[i].add(num)
            cols[j].add(num)
            boxes[box_idx].add(num)

            if dfs(idx + 1):
                return True

            board[i][j] = "."
            rows[i].remove(num)
            cols[j].remove(num)
            boxes[box_idx].remove(num)

        return False

    dfs(0)

回溯剪枝#

剪枝的目标是提前停止没有意义的搜索。常见剪枝包括：

剩余目标小于 0，直接返回。
排序后遇到同层重复元素，跳过。
当前路径长度已经超过限制，返回。
当前前缀在 Trie 中不存在，返回。

剪枝一定要保证不漏答案。比如组合去重里 i > start and nums[i] == nums[i - 1] 是"同层去重"，不能写成所有重复都跳过。

回溯常见模板#

组合/子集模板：

Python3 点击展开代码

6 lines 展开代码

def dfs(start):
    ans.append(path[:])
    for i in range(start, len(nums)):
        path.append(nums[i])
        dfs(i + 1)
        path.pop()

排列模板：

Python3 点击展开代码

12 lines 展开代码

def dfs():
    if len(path) == len(nums):
        ans.append(path[:])
        return
    for i in range(len(nums)):
        if used[i]:
            continue
        used[i] = True
        path.append(nums[i])
        dfs()
        path.pop()
        used[i] = False

图的遍历与染色#

图的表示方式#

常见图表示有两种：

邻接表：graph[u] 存所有从 u 能到达的点，适合稀疏图和大多数 LeetCode 图题。
邻接矩阵：matrix[i][j] 表示 i 和 j 是否相连，适合节点数较少或题目直接给矩阵。

邻接表和邻接矩阵#

边列表建邻接表时，无向图要加两条边，有向图只加一条边：

Python3 点击展开代码

4 lines 展开代码

graph = [[] for _ in range(n)]
for u, v in edges:
    graph[u].append(v)
    graph[v].append(u)  # 无向图才需要这一句

有向图和无向图#

无向图搜索重点是连通性和二分图。有向图除了连通性，还经常涉及环、依赖关系、拓扑排序。

图遍历中的 visited#

无向图一般用 visited 防止回头。有向图判环常用三色标记：0 未访问，1 当前路径中，2 已完成。

二分图判断#

LC785 - 判断二分图#

二分图是图恰好能分为两边的节点，左边全部指向右边。（如果能将一个图的节点集合分割成两个独立的子集 A 和 B ，并使图中的每一条边的两个节点一个来自 A 集合，一个来自 B 集合，就将这个图称为二分图。）

以下情况可考虑有二分图：

能不能把人/点分成两组，使得有关系的两个点不在同组
相邻节点不能有相同颜色
判断图是否可以用两种颜色染色
图中是否存在奇数环
敌对关系、互斥关系、分组问题

用DFS来判断二分图，可以用color数组给每个节点染色（1/-1），如果一个节点是1，邻居必须是-1，反之亦然。我们用这种方式走一条路径，如果和邻居撞色就失败了。我们从每个还没涂色的点进行dfs。

Python3 点击展开代码

23 lines 展开代码

def isBipartite(self, graph: list[list[int]]) -> bool:
    n = len(graph)
    # 默认都没涂色
    color = [0] * n

    def dfs(node, c):
        color[node] = c

        for nxt in graph[node]:
            if color[nxt] == 0:
                if not dfs(nxt, -c):
                    return False
            elif color[nxt] == c:
                return False

        return True

    for i in range(n):
        if color[i] == 0:
            if not dfs(i, 1):
                return False

    return True

LC886 - 可能的二分法#

我们用dislikes建图，然后看看能不能二分就可以了。

Python3 点击展开代码

25 lines 展开代码

from typing import List

def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool:
    graph = [[] for _ in range(n)]
    for d in dislikes:
        graph[d[0]-1].append(d[1]-1)
        graph[d[1]-1].append(d[0]-1)

    # 接下来，判断graph是否是二分图即可
    color = [0] * n 
    def dfs(node,c):
        color[node] = c
        for nxt in graph[node]:
            if color[nxt] == 0:
                if not dfs(nxt,-c):
                    return False
            elif color[nxt] == c:
                return False
        return True

    for i in range(n):
        if color[i] == 0:
            if not dfs(i,1):
                return False
    return True

克隆图#

LC133 - 克隆图#

数据结构的克隆，都是先建立旧节点-新节点的映射字典，然后用新.next = 新（旧.next）来解决。也就是传统做法，两轮法：

Python3 点击展开代码

26 lines 展开代码

class Node:
    def __init__(self,val = 0):
        self.val = val
        self.neighbors = []

def cloneGraph(self, node: Node) -> Node:
    if not node:
        return None

    originToClone = {}
    # DFS 遍历图
    def dfs(node:Node):
        if node in originToClone:
            return
        originToClone[node] = Node(node.val)
        for nxt in node.neighbors:
            dfs(nxt)
    
    dfs(node)

    # 开始克隆关系
    for origin, clone in originToClone.items():
        for nxt in origin.neighbors:
            clone.neighbors.append(originToClone[nxt])
    
    return originToClone[node]

我们可以在一次dfs中一遍创建克隆节点，一遍克隆邻居关系。

Python3 点击展开代码

26 lines 展开代码

class Node:
    def __init__(self, val=0, neighbors=None):
        self.val = val
        self.neighbors = neighbors if neighbors is not None else []


def cloneGraph(self, node: Node) -> Node:
    if not node:
        return None

    originToClone = {}

    # 每层dfs负责创建并返回clone节点，然后在dfs中也克隆关系
    def dfs(node):
        if node in originToClone:
            return originToClone[node]

        clone = Node(node.val)
        originToClone[node] = clone

        for nxt in node.neighbors:
            clone.neighbors.append(dfs(nxt))

        return clone

    return dfs(node)

图遍历常见模板#

无向图连通性：

Python3 点击展开代码

6 lines 展开代码

def dfs(node):
    if node in visited:
        return
    visited.add(node)
    for nxt in graph[node]:
        dfs(nxt)

有向图判环：

Python3 点击展开代码

11 lines 展开代码

def dfs(node):
    if state[node] == 1:
        return False
    if state[node] == 2:
        return True
    state[node] = 1
    for nxt in graph[node]:
        if not dfs(nxt):
            return False
    state[node] = 2
    return True

拓扑排序：有向无环图上的遍历#

什么是拓扑排序#

拓扑排序是把有向图中的节点排成一个线性顺序，使得每条边 u -> v 都满足 u 在 v 前面。它只存在于有向无环图中。

入度表和队列#

入度表示有多少条边指向当前节点。BFS 拓扑排序会先把所有入度为 0 的节点入队，然后每弹出一个节点，就把它指向的节点入度减 1。

DFS 拓扑排序#

DFS 拓扑排序通常用后序收集。一个节点的所有后继都处理完后，再把当前节点加入答案，最后把答案反转。

BFS 拓扑排序#

BFS 拓扑排序就是不断删除入度为 0 的节点。如果最后处理的节点数少于总节点数，说明图中有环。

课程表问题#

LC207 - 课程表#

这一题实际上就是判断有向图是否有环，我们先构成邻接表，然后一层一层剥下来。

Python3 点击展开代码

25 lines 展开代码

from collections import deque

def canFinish(self, numCourses: int, prerequisites: list[list[int]]) -> bool:
    graph = [[] for _ in range(numCourses)]
    indegree = [0] * numCourses
    for u,v in prerequisites:
        graph[v].append(u)
        indegree[u]+=1

    # 开始拓扑排序
    q = deque()
    for i in range(numCourses):
        if indegree[i] == 0:
            q.append(i)
    
    count = 0
    while q:
        course = q.popleft()
        count += 1
        for nxt in graph[course]:
            indegree[nxt] -= 1
            if indegree[nxt] == 0:
                q.append(nxt)
    
    return count == numCourses

有向图判环，也可以使用DFS染色。我们可以用三种状态来表示节点状态，0没访问、1当前递归路径、2已经访问完成确认安全。

Python3 点击展开代码

28 lines 展开代码

def canFinish(self, numCourses: int, prerequisites: list[list[int]]) -> bool:
    graph = [[] for _ in range(numCourses)]
    for u,v in prerequisites:
        graph[v].append(u)

    # 开始dfs
    visited = [0] * numCourses

    # 不碰到1，碰到2，就算完成任务。然后再给完成任务的节点标记为2。
    def dfs(course):
        if visited[course] == 1:
            return False
        if visited[course] == 2:
            return True
        
        visited[course] = 1

        for nxt in graph[course]:
            if not dfs(nxt):
                return False
        visited[course] = 2
        return True
    
    for i in range(numCourses):
        if visited[i] == 0:
            if not dfs(i):
                return False
    return True

LC210 - 课程表 II#

本题需要返回学习完的顺序，其实就是在拓扑排序的时候收集一下答案，把count换成ans即可。

Python3 点击展开代码

27 lines 展开代码

from collections import deque

def findOrder(self, numCourses: int, prerequisites: list[list[int]]) -> list[int]:
    graph = [[] for _ in range(numCourses)]
    indegree = [0] * numCourses
    for u,v in prerequisites:
        graph[v].append(u)
        indegree[u]+=1

    # 开始拓扑排序
    q = deque()
    for i in range(numCourses):
        if indegree[i] == 0:
            q.append(i)
    
    ans = []
    while q:
        course = q.popleft()
        ans.append(course)
        for nxt in graph[course]:
            indegree[nxt] -= 1
            if indegree[nxt] == 0:
                q.append(nxt)
    
    if len(ans) == numCourses:
        return ans
    return []

那么，同理，我们在dfs中多维持一个ans，也可以得到答案。不过顺序是反过来的。

Python3 点击展开代码

30 lines 展开代码

    graph = [[] for _ in range(numCourses)]
    for u,v in prerequisites:
        graph[v].append(u)

    # 开始dfs
    visited = [0] * numCourses
    ans = []

    # 不碰到1，碰到2，就算完成任务。然后再给完成任务的节点标记为2。
    def dfs(course):
        if visited[course] == 1:
            return False
        if visited[course] == 2:
            return True
        
        visited[course] = 1

        for nxt in graph[course]:
            if not dfs(nxt):
                return False
        visited[course] = 2
        # 后序收集
        ans.append(course)
        return True
    
    for i in range(numCourses):
        if visited[i] == 0:
            if not dfs(i):
                return []
    return ans[::-1]

LC802 - 找到最终的安全状态#

这一题说白了就是看从一个节点出发，有没有环。我们使用dfs比较方便。

Python3 点击展开代码

24 lines 展开代码

def eventualSafeNodes(self, graph: list[list[int]]) -> list[int]:
    n = len(graph)
    visited = [0] * n
    
    def dfs(node):
        if visited[node] == 1:
            return False
        if visited[node] == 2:
            return True
        
        visited[node] = 1

        for nxt in graph[node]:
            if not dfs(nxt):
                return False
        
        visited[node] = 2
        return True
    
    ans = []
    for i in range(n):
        if dfs(i):
            ans.append(i)
    return ans

拓扑排序常见模板#

BFS 拓扑排序：

Python3 点击展开代码

21 lines 展开代码

from collections import deque

graph = [[] for _ in range(n)]
indegree = [0] * n

for u, v in edges:
    graph[u].append(v)
    indegree[v] += 1

q = deque(i for i in range(n) if indegree[i] == 0)
order = []

while q:
    cur = q.popleft()
    order.append(cur)
    for nxt in graph[cur]:
        indegree[nxt] -= 1
        if indegree[nxt] == 0:
            q.append(nxt)

has_cycle = len(order) != n

DFS 判环：

Python3 点击展开代码

13 lines 展开代码

state = [0] * n

def dfs(node):
    if state[node] == 1:
        return False
    if state[node] == 2:
        return True
    state[node] = 1
    for nxt in graph[node]:
        if not dfs(nxt):
            return False
    state[node] = 2
    return True

搜索优化#

剪枝#

剪枝就是减少无意义分支。最常见的剪枝信号是：越界、已经访问、当前和超过目标、剩余数量不够、同层重复、前缀不存在。

记忆化搜索#

当 DFS 中同一个状态会被重复计算时，可以用字典或数组记忆化。典型状态包括 (i, j)、(idx, remain)、node 等。

状态压缩#

当状态里包含一组元素是否被使用，可以用二进制位压缩。比如 mask 的第 i 位表示第 i 个元素是否已经使用。

双向搜索#

双向搜索适合起点和终点都明确、分支很大的最短路问题，比如单词接龙。从两边同时扩展，可以显著减少搜索层数。

A* 搜索#

A* 是带启发式函数的最短路搜索。普通面试里不常考，知道它是在 Dijkstra/BFS 的基础上用估价函数优先探索更可能接近终点的状态即可。

搜索中的复杂度估算#

DFS/BFS 的复杂度通常看状态数和转移数。回溯题可以粗略估算为搜索树节点数；图遍历通常是 O(V + E)；网格遍历通常是 O(mn)。

搜索与遍历题目的分类判断#

看题目是否要求遍历所有节点#

如果题目问数量、面积、连通性，通常要遍历所有可能节点。

看题目是否要求最短步数#

无权图最短步数优先 BFS。

看题目是否需要枚举所有方案#

所有方案、所有组合、所有路径，一般是 DFS/回溯。

看题目是否存在重复状态#

有重复状态就要考虑 visited、记忆化或原地标记。

看题目是否需要撤销选择#

如果同一个元素在不同路径里还能被再次使用，需要回溯撤销选择。

看题目是否有方向和依赖关系#

有依赖关系通常建有向图；如果还要判断能不能完成，优先想到拓扑排序或 DFS 判环。

搜索与遍历常见模板#

二叉树 DFS 模板#

Python3 点击展开代码

5 lines 展开代码

def dfs(node):
    if not node:
        return
    dfs(node.left)
    dfs(node.right)

二叉树 BFS 模板#

Python3 点击展开代码

4 lines 展开代码

q = deque([root])
while q:
    for _ in range(len(q)):
        node = q.popleft()

图 DFS 模板#

Python3 点击展开代码

6 lines 展开代码

def dfs(node):
    if node in visited:
        return
    visited.add(node)
    for nxt in graph[node]:
        dfs(nxt)

图 BFS 模板#

Python3 点击展开代码

8 lines 展开代码

q = deque([start])
visited = {start}
while q:
    cur = q.popleft()
    for nxt in graph[cur]:
        if nxt not in visited:
            visited.add(nxt)
            q.append(nxt)

网格 DFS 模板#

Python3 点击展开代码

8 lines 展开代码

def dfs(i, j):
    if not (0 <= i < m and 0 <= j < n):
        return
    if is_blocked(i, j):
        return
    grid[i][j] = VISITED
    for dx, dy in directions:
        dfs(i + dx, j + dy)

网格 BFS 模板#

Python3 点击展开代码

6 lines 展开代码

q = deque([(sx, sy)])
visited = {(sx, sy)}
while q:
    x, y = q.popleft()
    for dx, dy in directions:
        nx, ny = x + dx, y + dy

回溯模板#

Python3 点击展开代码

7 lines 展开代码

def dfs(start):
    if 满足条件:
        ans.append(path[:])
    for i in range(start, len(nums)):
        path.append(nums[i])
        dfs(i + 1)
        path.pop()

拓扑排序模板#

Python3 点击展开代码

7 lines 展开代码

q = deque(i for i in range(n) if indegree[i] == 0)
while q:
    cur = q.popleft()
    for nxt in graph[cur]:
        indegree[nxt] -= 1
        if indegree[nxt] == 0:
            q.append(nxt)

搜索与遍历问题总结#

搜索与遍历题的本质是：先把题目抽象成节点和边，再决定用 DFS、BFS、回溯还是拓扑排序。DFS 适合深入和枚举，BFS 适合最短路和扩散，回溯适合所有方案，拓扑排序适合有向依赖。写代码时只要抓住状态、选择、出口、去重和剪枝，绝大多数题都能落到固定模板上。