[!info] related notes 算法面试题型 MOC 回溯算法 二叉树层序遍历

DFS / BFS / 回溯

一句话区分

• DFS：一路走到黑，再回来换路。
• BFS：一层一层往外扩散。
• 回溯：带撤销操作的 DFS，用来找“所有可能解 / 满足条件的方案”。

理解方式：

• DFS / BFS：搜索方式（遍历顺序）
• 回溯：解题框架（通常建立在 DFS 上）

DFS（深度优先搜索）

1) 是什么

从一个点出发，优先向更深的方向搜索；走不动就回退，换一条路继续。

2) 怎么写

递归（最常见）：

def dfs(node):
    if node is None:
        return

    # process node
    for nxt in node.neighbors:
        dfs(nxt)

显式栈（等价于递归栈）：

def dfs(start):
    stack = [start]
    visited = set()
    while stack:
        node = stack.pop()
        if node in visited:
            continue
        visited.add(node)
        for nxt in node.neighbors:
            if nxt not in visited:
                stack.append(nxt)

3) 什么时候用

• 遍历树/图：前中后序、连通块、岛屿问题
• 判断路径是否存在、枚举路径（不要求最短）
• 状态空间搜索：排列/子集/N 皇后/数独（通常就是回溯）

4) 容易混淆的点

• 有环图必须 visited，否则会死循环。
• DFS 不保证最短路径（无权最短路优先 BFS）。
• 深度可能很大时注意递归爆栈，改显式栈或控制深度。

5) 经典例子

二叉树先序遍历（DFS）：

def preorder(root):
    if not root:
        return
    preorder(root.left)
    preorder(root.right)

BFS（广度优先搜索）

1) 是什么

从起点出发，按距离分层：先访问距离为 1 的点，再访问距离为 2 的点 …

2) 怎么写

队列 + visited：

from collections import deque

def bfs(start):
    q = deque([start])
    visited = {start}
    while q:
        node = q.popleft()
        for nxt in node.neighbors:
            if nxt not in visited:
                visited.add(nxt)
                q.append(nxt)

按层处理（典型用于“层序遍历/最少层数”）：

from collections import deque

def level_order(root):
    if not root:
        return []
    q = deque([root])
    res = []
    while q:
        size = len(q)
        level = []
        for _ in range(size):
            node = q.popleft()
            level.append(node.val)
            if node.left:
                q.append(node.left)
            if node.right:
                q.append(node.right)
        res.append(level)
    return res

3) 什么时候用

• 无权图最短路：第一次到达目标点就是最少边数/步数
• 最少步数/最少操作次数/几层到达
• 扩散模型：感染/腐烂橘子/多源 BFS
• 层序遍历：树的按层输出

4) 容易混淆的点

• BFS 可能更耗内存：同一层节点数可能很大。
• “按层”就必须固定 size = len(queue)，否则层会混掉。

5) 经典例子

• 二叉树层序遍历

回溯（Backtracking）

1) 是什么

回溯 = DFS + 选择 + 撤销（恢复现场）+ 剪枝。

核心动作：

做选择
递归
撤销选择

2) 怎么写

模板：

res = []
path = []

def backtrack(choices):
    if end_condition:
        res.append(path[:])
        return

    for choice in choices:
        if not valid(choice):
            continue

        path.append(choice)     # choose
        backtrack(next_choices) # explore
        path.pop()              # un-choose

3) 什么时候用

• 所有方案：全排列/组合/子集
• 切割与构造：回文切割、括号生成
• 棋盘/网格：N 皇后、数独、单词搜索

4) 容易混淆的点

• 回溯一定有“状态恢复”，普通 DFS 遍历树不一定需要。
• 保存答案要 res.append(path[:])，不要 res.append(path)。
• 回溯常超时：关键在剪枝、去重（排序 + 跳过重复）、状态表示。

visited / used / path 常见含义：

• visited：图搜索判重（防环/防走回头路）
• used：排列类回溯中元素是否被当前路径使用
• path：当前已做出的选择序列

5) 经典例子

全排列（元素只能用一次）：

def permute(nums):
    res = []
    path = []
    used = [False] * len(nums)

    def dfs():
        if len(path) == len(nums):
            res.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

    dfs()
    return res

选择口诀

• 选 BFS：最短、最少、层序、扩散
• 选 DFS：遍历、连通、深搜、路径存在
• 选回溯：所有方案、排列组合、试了再撤销