回溯算法图解与实战：从《Hello 算法》二叉树前序遍历到通用解题框架

回溯算法（Backtracking Algorithm）是解决搜索、约束满足与组合优化问题的核心算法思想之一。本文基于《Hello 算法》日本語版回溯算法章节展开，以三个递进的二叉树例题讲透“尝试—回退—剪枝”的本质，并提炼出可直接套用的通用框架代码。读完本文，你将掌握如何用深度优先搜索遍历解空间、如何在递归中正确保存与恢复状态，以及如何把全排列、n 皇后等经典问题统一映射到同一套回溯模板中。

什么是回溯算法

回溯算法本质上是通过暴力穷举（総当たり）求解问题的方法：从初始状态出发，把问题所有可能的解“力尽”地探索一遍，遇到正确的解就记录下来，直到找出全部解，或试完所有选择仍无解为止。

用更形式化的话说，回溯算法在解空间（Solution Space）中做搜索，而绝大多数实现都建立在深度优先搜索（DFS）之上。正如《Hello 算法》“二叉树”章节所讲，二叉树的前序、中序、后序遍历都属于深度优先搜索，因此本书直接以前序遍历为入口来构造回溯问题，让读者借助熟悉的树结构逐步理解回溯的运转机理。

例题一：前序遍历搜索指定节点

作为第一个观察窗口，章节先给出最朴素的问题：

例题一：给定一棵二叉树，找出并记录其中所有值为 7 的节点，返回这些节点的列表。

做法是对树做前序遍历，每到一个节点判断其值是否为 7，若是则把节点追加进结果列表 res。核心代码如下（节选自 preorder_traversal_i_compact.py）：

def pre_order(root: TreeNode):
    """前序遍历：例题一"""
    if root is None:
        return
    if root.val == 7:
        # 记录解
        res.append(root)
    pre_order(root.left)
    pre_order(root.right)

图中虚线箭头描述的就是整棵树的深度优先访问顺序：从根出发一路向左下沉，到达叶子后回溯到父节点再进入右子树。此时“搜索”只是单纯的遍历加判定，还不存在真正意义上的状态撤销，但我们已经可以从中观察到回溯的两个雏形动作——“尝试”与“回退”：访问每个节点对应一次“尝试”，越过叶节点或由 return 返回父节点则对应一次“回退”。

尝试与回退：为什么要保存并还原状态

这里章节特意强调一个关键结论：“回退”绝不等于函数中的 return。return 只是从当前递归帧退出，若我们真正“做了选择”并想回到做选择之前的状态，就必须显式地把状态还原回去。为此，章节把例题一向前推进一步。

例题二：在二叉树中搜索所有值为 7 的节点，并返回从根节点到这些节点的路径。

实现上只需引入一个路径列表 path 记录“已经访问过的节点”。一旦遇到值为 7 的节点，就把当前 path 复制一份存入结果 res。关键在于：每次尝试（进入新节点）先把节点压入 path，而在准备退回父节点之前，必须把该节点从 path 中弹出，恢复为本次尝试之前的状态。对应实现见 preorder_traversal_ii_compact.py：

def pre_order(root: TreeNode):
    """前序遍历：例题二"""
    if root is None:
        return
    # 尝试
    path.append(root)
    if root.val == 7:
        # 记录解
        res.append(list(path))
    pre_order(root.left)
    pre_order(root.right)
    # 回退
    path.pop()

这里有两个极其重要的工程细节：

1. 浅拷贝快照：res.append(list(path)) 必须拷贝一份 path。若直接 res.append(path)，由于 path 后续还会被 pop 修改，最终 res 中所有记录都会指向同一份“被复原”的空列表，导致结果全部丢失。
2. 先做选择、后做撤销：append 与 pop 必须严格围绕递归调用“对称”出现。任何一侧遗漏，都会让路径状态在兄弟子树之间相互污染。

尝试与回退可以形象地理解为互为逆操作的“前进一步”与“撤销一步”，path 的压栈/弹栈恰好对应了搜索树上的向下深入与向上回溯。章节用 11 张分步图（preorder_find_paths_step1.png ~ step11，位于 backtracking_algorithm.assets）完整演示了该树上前序访问时 path 的每一次增长与缩短，读者可对照动画般的图序自行推演。

剪枝：用约束砍掉无效分支

真实世界的回溯问题通常带有一个或多个约束条件，而这些约束最直接的用途就是剪枝（Pruning）。

例题三：在二叉树中搜索所有值为 7 的节点并返回根到它们的路径，但路径中不得包含值为 3 的节点。

为满足该约束，只需在进入节点前做一次拦截：一旦当前节点值为 3，立刻 return，不再深入其子树。实现见 preorder_traversal_iii_compact.py：

def pre_order(root: TreeNode):
    """前序遍历：例题三"""
    # 剪枝
    if root is None or root.val == 3:
        return
    # 尝试
    path.append(root)
    if root.val == 7:
        # 记录解
        res.append(list(path))
    pre_order(root.left)
    pre_order(root.right)
    # 回退
    path.pop()

“剪枝”是一个非常形象的比喻：搜索过程中一旦遇到不满足约束的分支，就把这棵分支“整支剪掉”，不再为它浪费任何尝试。

如上图所示，值为 3 的节点一旦被访问，其左右子树（图中灰虚线断开的 6 与 7）便整体不再进入搜索。剪枝直接决定了回溯算法的实际效率：同样的解空间，剪枝越早、越强，无效计算越少。

通用回溯框架：state、choices 与五个子过程

如果把例题三中的“尝试、回退、剪枝”抽离出来，把“求解特定树问题”的细节去掉，就能归纳出一个可用于任何回溯问题的通用代码框架。框架只依赖四个抽象角色：

• state：当前问题状态，包含已经做出的选择（例题中就是已走过的路径 path）；
• choices：当前状态下可做的全部选择（例题中就是当前节点的左、右子节点）；
• res：存放解的列表；
• 若干判定函数：判断是否为解、判断选择是否合法、执行/撤销选择。

以 Python 为代表的通用骨架如下：

def backtrack(state: State, choices: list[Choice], res: list[State]):
    """回溯算法框架"""
    # 判断是否为解
    if is_solution(state):
        # 记录解
        record_solution(state, res)
        # 不再继续搜索
        return
    # 遍历所有选择
    for choice in choices:
        # 剪枝：判断选择是否合法
        if is_valid(state, choice):
            # 尝试：做出选择，更新状态
            make_choice(state, choice)
            backtrack(state, choices, res)
            # 回退：撤销选择，恢复到之前的状态
            undo_choice(state, choice)

对照例题三（见 preorder_traversal_iii_template.py），各抽象函数被一一具象化：

• is_solution：当前状态非空且路径末端节点值为 7；
• record_solution：把当前状态（路径）拷贝后加入 res；
• is_valid：该选择非空且值不等于 3（剪枝判定）；
• make_choice：把选择节点追加进 state；
• undo_choice：从 state 弹出末尾节点；
• 进入下一层时把 choices 更新为 [choice.left, choice.right]。

入口调用只需 backtrack(state=[], choices=[root], res=res)。

为说明该框架在不同语言中的落地形态，下面补充两个有代表性的实现视角。C++ 版与抽象骨架几乎一一对应（源自 preorder_traversal_iii_template.cpp 所属的示例集）：

void backtrack(State *state, vector<Choice *> &choices, vector<State *> &res) {
    if (isSolution(state)) {
        recordSolution(state, res);
        return;
    }
    for (Choice choice : choices) {
        if (isValid(state, choice)) {
            makeChoice(state, choice);
            backtrack(state, choices, res);
            undoChoice(state, choice);
        }
    }
}

而 C 语言由于缺少语言自带的动态列表，采用了静态数组 + 长度游标的经典做法（见 preorder_traversal_iii_template.c）：用 path[pathSize++] = choice 完成入栈（尝试），用 pathSize-- 完成弹栈（回退），以 path[pathSize-1]->val == 7 判定解，choices 以 {choice->left, choice->right} 的定长数组在递归间传递。这种“数组 + 下标”的实现能帮助读者看清回溯真正消耗的资源其实是递归调用栈与路径存储。

在同一章节示例集中，Java、C#、Go、Swift、JS、TS、Dart、Rust、Kotlin、Ruby 均提供了结构完全同构的实现，读者可在 ja/codes 对应语言的 chapter_backtracking/ 目录下逐一对照，体会不同语言表达“状态修改与撤销”的语法差异（如 Go 的指针切片、Swift 的 inout 参数、Rust 的 &mut 借用等）。

模板化实现中一个容易踩的坑：保留还是删除 return

将例题三套入框架后会发现：问题要求在找到值为 7 的节点后继续向下搜索（因为后续仍可能出现其他值为 7 的节点），因此模板中“记录解之后的 return 必须删除”，否则一旦命中第一个目标就会中止整条分支的继续探索。

上图的对比非常直观：左侧“保留 return”，记录解后立即用“剪刀”截断后续路径；右侧“删除 return”，记录解后继续深入，才能把整棵树中所有满足条件的路径全部搜出来。“找到一个解后要不要立即返回”完全取决于问题要求的是“一个解”还是“所有解”——这是套用模板时必须先想清楚的问题。

模板写法相比紧凑的前序遍历实现略显冗长，但换来的是通用性：绝大多数回溯题只需按具体问题定义好 state、choices，再实现 is_solution / record_solution / is_valid / make_choice / undo_choice 五个子过程即可完成求解。

回溯的常用术语

为了精确描述与分析算法题，章节归纳了回溯领域的核心术语及其在例题三中的对应实例，对照关系如下：

术语	定义	例题三中的对应
解（Solution）	满足问题特定条件的答案，可能存在一个或多个	从根到节点 7 的所有满足约束的路径
约束条件（Constraint）	限制解可行性的条件，通常用于剪枝	路径中不得包含值为 3 的节点
状态（State）	表示某一时刻的问题情形，包含已做的选择	当前已访问的路径，即 path 节点列表
尝试（Attempt）	基于可用选择探索解空间的过程，包含选择、更新状态、判断解	递归访问左右子节点、把节点加入 path、判断值是否为 7
回退（Backtracking）	遇到不满足约束的状态时撤销已做选择、返回之前状态	越过叶节点、结束访问或遇到值为 3 的节点时返回上层
剪枝（Pruning）	依据问题性质或约束避免无意义路径、提高效率的方法	遇到值为 3 的节点便不再继续深入

这些术语是高度通用的抽象：问题（problem）、解（solution）、状态（state）等概念不仅出现在回溯中，也贯穿分治、动态规划、贪心等算法范式，是贯穿整本书的分析语言。

回溯算法的优势与局限

回溯算法的本质是深度优先地穷举解空间，因此它的优势与短板同样鲜明。

优势在于：理论上它能找出满足条件的所有解；只要剪枝设计得当，就能大幅压缩无效搜索，在不少场景下保持可观效率。

局限同样不可回避，面对规模较大或结构复杂的问题，回溯的代价常常难以接受：

• 时间：通常需要遍历状态空间的全部可能性，时间复杂度可能高达指数级乃至阶乘级；
• 空间：递归过程需要持续保存当前状态（路径、剪枝辅助变量等），递归深度大时空间占用同样可观。

即便如此，对一部分搜索与约束满足问题而言，回溯依然是最合适的解法——因为在解出之前我们无法预测哪条选择能通向有效解，只能把所有可能都试一遍。此时真正的较量在于如何把效率优化到极致，两条代表性路线是：

• 剪枝：对确定无法产生解的路径直接放弃探索，节省时间与空间；
• 启发式搜索：在搜索过程中引入策略或估值，优先深入最可能产生有效解的分支。

回溯的典型应用场景

回溯算法被广泛用于三类问题。章节中列出的经典题例，大多在《Hello 算法》中配有完整的图解推导与多语言代码，可作延伸阅读。

第一类：搜索问题——目标是找出满足特定条件的所有解。

• 全排列问题：给定集合，求其全部排列（对应 permutations_problem.md，代码见 permutations_i.py、permutations_ii.py）；
• 子集和问题：给定集合与目标和，找出所有和为目标值的子集（对应 subset_sum_problem.md）；
• 汉诺塔问题：三根柱子上移动大小不同的圆盘，每次只能移动一个且大盘不能压在小盘上（对应 hanota_problem.md）。

第二类：约束满足问题——目标是找出满足全部约束的解。

• n 皇后问题：在 n×n 棋盘放置 n 个皇后使彼此不攻击（对应 n_queens_problem.md）；
• 数独：在 9×9 网格填入 1~9，使每行、每列及每个 3×3 宫格不重复；
• 图着色问题：用尽可能少的颜色为无向图着色，使相邻顶点颜色不同。

第三类：组合优化问题——目标是在组合空间中寻找满足条件的最优解。

• 0-1 背包问题：在容量限制下选取物品使总价值最大；
• 旅行商问题（TSP）：从某顶点出发访问其余顶点各一次并返回起点，求最短路径；
• 最大团问题：在无向图中找出两两相连的最大完全子图。

需要特别提醒的是：很多组合优化问题的“最优解”并不适合用回溯求得。例如 0-1 背包通常用动态规划换取更高时间效率，旅行商作为著名的 NP-Hard 问题常采用遗传算法、蚁群优化等元启发式方法，最大团问题则可用贪心等启发式求解。回溯在这些问题上更适合作为理解问题结构的起点，而非工程上的最终手段。

小结

回溯算法 = 解空间上的深度优先搜索 + 状态的显式保存与撤销 + 约束驱动的剪枝。从《Hello 算法》的递进例题可以看到，三个例题正好对应回溯的三大构成要素：

• 例题一建立了“DFS 即搜索”的直觉；
• 例题二揭示了“尝试必须配对称的回退、记录必须做拷贝”的状态管理纪律；
• 例题三展示了“约束即刻转为剪枝”的性能关键；
• 而通用框架把这一切收敛为 state / choices / res 加五个子函数的标准形态，让 n 皇后、全排列、子集和等难题都有了统一的解题入口。

若想继续深入，可顺藤摸瓜阅读同一章节下的 permutations_problem.md、subset_sum_problem.md 与 n_queens_problem.md，并在 ja/codes 的 chapter_backtracking/ 目录中运行对应语言的示例，亲手观察 path 的每一次进出栈。