Hello 算法回溯算法详解：从二叉树前序遍历到“尝试-回退-剪枝”通用框架

回溯算法（backtracking algorithm）是一种通过穷举搜索解空间来求解问题的方法，其核心机制是“尝试、回退、剪枝”。本文以 hello-algo 仓库回溯章节的 backtracking_algorithm.md 为主体，配合仓库中 Python、C++ 等语言的配套实现，带你从一道二叉树搜索例题出发，逐步推导出可复用于全排列、N 皇后、子集和等经典问题的回溯框架代码，并掌握如何根据约束条件剪枝以控制指数级搜索的开销。

一、什么是回溯算法：穷举 + 深度优先搜索

回溯算法的核心思想是：从一个初始状态出发，暴力搜索所有可能的解决方案，当遇到正确的解则将其记录，直到找到解或者尝试了所有可能的选择都无法找到解为止。它通常采用“深度优先搜索（DFS）”来遍历解空间——二叉树的前序、中序、后序遍历本质上都是深度优先搜索，回溯算法正是建立在这类遍历行为之上。

例题一：搜索所有值为 7 的节点

给定一棵由 [1, 7, 3, 4, 5, 6, 7] 构建的二叉树，要求搜索并记录所有值为 7 的节点，返回节点列表。解法是前序遍历，判断当前节点值是否为 7，若是则加入结果列表 res。仓库中对应的 Python 实现在 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)

驱动代码中通过 list_to_tree([1, 7, 3, 4, 5, 6, 7]) 初始化测试树，运行后可直接打印所有值为 7 的节点（见 preorder_traversal_i_compact.py 的 __main__ 部分）。

二、尝试与回退：回溯名字的由来

之所以称之为回溯算法，是因为该算法在搜索解空间时会采用“尝试”与“回退”的策略：当算法在搜索过程中遇到某个状态无法继续前进或无法得到满足条件的解时，它会撤销上一步的选择，退回到之前的状态，并尝试其他可能的选择。对例题一而言，访问每个节点代表一次“尝试”，而越过叶节点或返回父节点的 return 则表示“回退”。

值得注意的是，回退并不仅仅包括函数返回。对例题一稍作拓展：

例题二：返回根节点到值为 7 节点的路径

此时需要一个列表 path 记录访问过的节点路径。访问到值为 7 的节点时，复制 path 并添加进结果列表 res；遍历完成后，res 中保存的就是所有解。仓库实现见 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()

两处改动体现了尝试/回退的完整语义：

• 尝试：每次递归访问节点时，先将当前节点 append 进 path，把状态向前推进一格；
• 回退：递归返回前执行 path.pop()，将节点从 path 中弹出，恢复本次尝试之前的状态。

可以把尝试和回退理解为“前进”与“撤销”两个互为逆向的操作：记录解时的 res.append(list(path)) 必须复制 path（list(path)），因为 path 会在后续回退中被修改，若直接引用则结果会被污染。

三、剪枝：利用约束条件裁掉无效分支

复杂的回溯问题通常包含一个或多个约束条件，约束条件通常可用于“剪枝”。继续拓展例题：

例题三：路径中不包含值为 3 的节点

为了满足该约束，需要在搜索过程中添加剪枝操作：遇到值为 3 的节点时提前返回，不再继续搜索其子树。仓库实现见 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()

相比例题二，唯一变化是把剪枝判断前置到函数入口 if root is None or root.val == 3: return。在下图中，以节点 3 为根的整棵子树（3、6、7）被“剪掉”，避免了大量无意义的尝试，从而提高了搜索效率：

四、通用框架代码：state / choices / res 三要素

在掌握“尝试、回退、剪枝”之后，可以将其提炼为一个通用框架。框架中 state 表示问题的当前状态，choices 表示当前状态下可以做出的选择，res 为结果集（原文档以 Python、C++、Java、C#、Go、Swift、JS、TS、Dart、Rust、C、Kotlin、Ruby 十余种语言给出了同构实现）。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)

框架包含五个待实现的钩子函数：is_solution（判解）、record_solution（记录解）、is_valid（剪枝/合法性判断）、make_choice（尝试）、undo_choice（回退）。

基于框架求解例题三

对应仓库中 preorder_traversal_iii_template.py，各钩子的定义非常直观：

钩子	定义（Python 源码）	语义
is_solution	state and state[-1].val == 7	路径末尾节点值为 7
record_solution	res.append(list(state))	复制当前路径入结果集
is_valid	choice is not None and choice.val != 3	剪枝：排除值为 3 的节点
make_choice	state.append(choice)	尝试：把选择加入路径
undo_choice	state.pop()	回退：弹出路径末尾

主函数 backtrack 的递归过程见 preorder_traversal_iii_template.py：

def backtrack(
    state: list[TreeNode], choices: list[TreeNode], res: list[list[TreeNode]]
):
    """回溯算法：例题三"""
    # 检查是否为解
    if is_solution(state):
        # 记录解
        record_solution(state, res)
    # 遍历所有选择
    for choice in choices:
        # 剪枝：检查选择是否合法
        if is_valid(state, choice):
            # 尝试：做出选择，更新状态
            make_choice(state, choice)
            # 进行下一轮选择
            backtrack(state, [choice.left, choice.right], res)
            # 回退：撤销选择，恢复到之前的状态
            undo_choice(state, choice)

调用入口为 backtrack(state=[], choices=[root], res=res)，即初始状态为空路径，初始选择集只包含根节点；每进入一层递归，choices 收缩为当前节点的左、右子节点。

C++ 侧的同构实现在 preorder_traversal_iii_template.cpp，其中 nextChoices{choice->left, choice->right} 的写法与 Python 版本完全对应，可对照阅读以理解“下一轮选择集”的传递方式。

关键细节：记录解之后是否 return

原文档框架中，is_solution 命中后会执行 return 终止本分支的搜索。但对例题三，题意要求找到值为 7 的节点后仍要继续搜索其子树，因此模板实现中刻意删除了记录解之后的 return（对比 preorder_traversal_iii_template.py 中 if is_solution(state): 分支内只有 record_solution 而没有 return）。两种写法的差异在于：

• 保留 return：记录解后停止搜索，节点 7 的子树不再访问；
• 删除 return：记录解后不返回，继续遍历子节点，因此 1 -> 7 -> 4 -> 7 这类更长路径也能被找到。

这一细节是回溯框架应用中最容易踩坑的地方：框架里的 return 只在“找到一个解即可”的场景下正确；若要求“找到所有解”，则判解分支只记录、不返回。

相比直接基于前序遍历的实现，框架版代码虽然显得啰嗦，但通用性更好——许多回溯问题都可在该框架下解决，只需根据具体问题定义 state 和 choices，并实现框架中的各个钩子函数。

五、常用术语速查表

为清晰分析算法问题，原文档总结了一套回溯术语，并对照例题三给出实例：

名词	定义	例题三中的对应
解（solution）	满足问题特定条件的答案，可能有一个或多个	根节点到节点 7 的满足约束条件的所有路径
约束条件（constraint）	限制解的可行性的条件，通常用于剪枝	路径中不包含节点 3
状态（state）	问题在某一时刻的情况，包括已经做出的选择	当前已访问的节点路径，即 path 节点列表
尝试（attempt）	根据可用选择探索解空间的过程，包括做出选择、更新状态、检查是否为解	递归访问左（右）子节点，将节点添加进 path，判断节点的值是否为 7
回退（backtracking）	遇到不满足约束条件的状态时，撤销前面做出的选择，回到上一个状态	当越过叶节点、结束节点访问、遇到值为 3 的节点时终止搜索，函数返回
剪枝（pruning）	根据问题特性和约束条件避免无意义的搜索路径的方法，可提高搜索效率	遇到值为 3 的节点时不再继续搜索

需要说明：问题、解、状态等概念是通用的，在分治、回溯、动态规划、贪心等算法中都会涉及。

六、优点与局限性

回溯算法本质上是一种深度优先搜索算法，它尝试所有可能的解决方案直到找到满足条件的解。其优点在于能够找到所有可能的解决方案，且在合理的剪枝操作下效率很高。然而在处理大规模或复杂问题时，运行效率可能难以接受：

• 时间：回溯算法通常需要遍历状态空间的所有可能，时间复杂度可达指数阶或阶乘阶；
• 空间：递归调用中需保存当前状态（路径、剪枝用的辅助变量等），深度很大时空间需求也会显著增大。

即便如此，回溯算法仍是某些搜索问题和约束满足问题的最佳方案。由于无法预测哪些选择可生成有效解，只能遍历所有可能选择，此时关键是优化效率，常见手段有两种：

• 剪枝：避免搜索肯定不会产生解的路径，节省时间和空间；
• 启发式搜索：引入策略或估计值，优先搜索最可能产生有效解的路径。

七、回溯典型例题

回溯算法可用于解决许多搜索问题、约束满足问题和组合优化问题：

搜索问题（找到满足特定条件的解决方案）：

• 全排列问题：给定一个集合，求出其所有可能的排列组合（仓库实现见 permutations_i.py）；
• 子集和问题：给定集合与目标和，找到所有和为目标和的子集（实现见 subset_sum_i.py）；
• 汉诺塔问题：三根柱子上移动圆盘，每次移动一个且大圆盘不能压在小圆盘上。

约束满足问题（找到满足所有约束条件的解）：

• N 皇后：在 n × n 棋盘上放置 n 个皇后使它们互不攻击（实现见 n_queens.py）；
• 数独：在 9 × 9 网格中填入数字 1~9，使每行、每列和每个 3 × 3 子网格中数字不重复；
• 图着色问题：用最少的颜色给无向图顶点着色，使相邻顶点颜色不同。

组合优化问题（在组合空间中找到满足条件的最优解）：

• 0-1 背包问题：容量限制内选择物品使总价值最大；
• 旅行商问题：访问所有点恰好一次后返回起点，求最短路径；
• 最大团问题：找到无向图中最大的完全子图。

需要特别注意，对于许多组合优化问题，回溯并非最优解法：0-1 背包问题通常使用动态规划以获得更高的时间效率；旅行商是著名的 NP-Hard 问题，常用遗传算法、蚁群算法等；最大团问题则可借助贪心等启发式算法求解。

八、如何查看与运行配套代码

以上全部代码均随仓库提供，Python 实现集中在 codes/python/chapter_backtracking/ 目录下，每个文件均可直接运行（依赖同仓库 codes/python/modules/ 中的 TreeNode、list_to_tree、print_tree 工具函数）：

python codes/python/chapter_backtracking/preorder_traversal_iii_template.py

运行后会先打印初始化后的二叉树，再输出所有满足约束的路径，可逐行对照本文的框架讲解。同一目录下的 preorder_traversal_i/ii/iii_compact.py 分别对应例题一、二、三的紧凑实现。其他语言版本可在 codes/ 下的 cpp、java、go、rust、typescript 等语言的 chapter_backtracking 目录中找到同名文件，C++ 与 Python 的钩子函数命名（isSolution/is_solution 等）一一对应，便于跨语言对照理解。