Hello 算法实战：回溯算法框架下的二叉树路径搜索（preorder_traversal_iii_template 模板代码全解析）

Hello 算法实战：回溯算法框架下的二叉树路径搜索（preorder_traversal_iii_template 模板代码全解析）

【免费下载链接】hello-algo《Hello 算法》：动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語，提供 Python, Java, C++, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo

本文以《Hello 算法》回溯章节的经典例题三为核心，围绕仓库中以preorder_traversal_iii_template命名的回溯算法框架（模板）实现展开。你将看到：同样的"二叉树中搜索所有值为 7、且路径不含值为 3 的节点"问题，如何从直接递归的朴素解法，被重构为"判断解—记录解—剪枝—尝试—回退"五段式通用框架；每个框架子函数在源码中的职责是什么；以及如何在本仓库中查看可交互执行与逐步可视化的完整版本。读完你不仅能独立跑通这段代码，还能把同一套框架思想迁移到全排列、N 皇后等其它回溯问题上。

例题三：问题定义与回溯三要素

在《Hello 算法》中文文档 backtracking_algorithm.md 中，例题三被定义为：

在二叉树中搜索所有值为 $7$ 的节点，请返回根节点到这些节点的路径，并要求路径中不包含值为 $3$ 的节点。

回溯算法本质上是从初始状态出发、通过穷举搜索解空间并记录可行解的算法，通常以深度优先搜索（DFS）遍历解空间，而二叉树的前序遍历正是一种 DFS。例题三相较于前两个例题多出的价值在于：它同时覆盖了回溯的**尝试（尝试沿着某条边继续前进）、回退（撤销上一步选择恢复现场）与剪枝（拒绝不满足约束的搜索分支）**三个核心动作。

值为 3 的节点就是约束条件所在。当搜索走到值为 3 的节点时，该节点以及它的整棵子树都不可能再出现在合法路径中，应当"提前返回、不再深入"——这一步在文档中被称为剪枝（pruning）。

从朴素递归到框架实现：为什么需要模板化

章节文档在给出例题三的"精简版"直接递归解法后，随即引入了 框架代码：将回溯的"尝试、回退、剪枝"主体结构抽象为一种通用骨架，提升代码在不同题目间的可复用性。

框架代码规定了解题的五个固定步骤：

1. 判断是否为解（is_solution）：若当前状态满足题目要求，则记录；
2. 记录解（record_solution）：把当前状态快照存入结果集；
3. 遍历所有选择（遍历choices）并对每个选择剪枝（is_valid）：不合法就跳过；
4. 尝试（make_choice）：做出选择、更新状态；
5. 回退（undo_choice）：撤销选择、恢复到进入该选择前的状态。

其中state表示问题的当前状态，choices表示当前状态下可以做出的选择，res用于收集所有解。框架的好处是：一旦搭好骨架，解决新问题时只需定义好state与choices的具体含义、实现对应的子函数即可，主递归过程几乎不用改动。

需要特别指出一个与通用骨架的差异：通用框架在record_solution后会执行return（记录一个解即停止当前分支），而例题三要求找到所有路径，因此记录解后不能返回，必须继续向更深层搜索。这一点在俄文版章节文档 ru/.../backtracking_algorithm.md 中有明确说明：找到值为 7 的节点后仍需继续搜索，故记录解后的return需要删除。

源码级拆解：preorder_traversal_iii_template 逐函数精讲

仓库根目录下的 Python 主实现位于 codes/python/chapter_backtracking/preorder_traversal_iii_template.py，俄文语料对应副本位于 ru/codes/python/chapter_backtracking/preorder_traversal_iii_template.py。其完整代码如下：

def is_solution(state: list[TreeNode]) -> bool: """判断当前状态是否为解""" return state and state[-1].val == 7 def record_solution(state: list[TreeNode], res: list[list[TreeNode]]): """记录解""" res.append(list(state)) def is_valid(state: list[TreeNode], choice: TreeNode) -> bool: """判断在当前状态下，该选择是否合法""" return choice is not None and choice.val != 3 def make_choice(state: list[TreeNode], choice: TreeNode): """更新状态""" state.append(choice) def undo_choice(state: list[TreeNode], choice: TreeNode): """恢复状态""" state.pop() 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)

对照五步骨架，逐函数看它的职责与本例的特殊设计：

• is_solution（判断解）：state保存的是当前走过的节点路径，最后一个节点值等于 7 即认为到达目标节点。这里利用state and ...短路处理了state为空的情况。
• record_solution（记录解）：res.append(list(state))。注意必须用list(state)做一次浅拷贝快照，而不是直接 appendstate本身——因为后续的尝试/回退会原地修改state，直接引用会导致所有已记录路径被后续操作污染。
• is_valid（剪枝）：本例题唯一的约束。choice is not None拦截空子树，choice.val != 3则把值为 3 的节点及其子树整体排除出搜索空间。
• make_choice/undo_choice（尝试与回退）：一对互逆操作。进入一个节点前append入栈，递归返回后pop出栈，保证兄弟分支之间路径状态互不干扰。这正是"尝试与回退互为逆向"在框架层的落实。
• backtrack（递归主流程）：关键在递归参数[choice.left, choice.right]——它把"下一步候选"定义为当前节点的左右子节点，与二叉树的结构天然对应；res则在整个递归过程中共享。这与通用骨架中"从同一候选集中反复选择"（如全排列问题每层都从剩余元素中选）形成对比，说明choices的具体语义完全由题目决定。

值得强调的是，例题三的实现没有在record_solution后写return。若保留return，一旦找到某个值为 7 的节点就立刻回退，会漏掉该节点子树中可能存在的其它目标节点（例如"7 的子孙仍是 7"的路径）；删除return才能保证收集到全部解。

运行验证：驱动代码与期望输出

backtrack的调用入口位于同一文件 driver 段：

if __name__ == "__main__": root = list_to_tree([1, 7, 3, 4, 5, 6, 7]) print("\n初始化二叉树") print_tree(root) # 回溯算法 res = [] backtrack(state=[], choices=[root], res=res) print("\n输出所有根节点到节点 7 的路径，要求路径中不包含值为 3 的节点") for path in res: print([node.val for node in path])

其中list_to_tree按"数组第 $i$ 个节点的左子为 $2i+1$、右子为 $2i+2$"的层序规则建树（该工具函数来自 modules）。输入的[1, 7, 3, 4, 5, 6, 7]对应的二叉树为：

1 / \ 7 3 / \ / \ 4 5 6 7

不难推演整个搜索过程与最终结果：

• 根节点 1 的两个候选中，右子 3 被is_valid剪掉，整棵右子树（含值为 7 的节点）不再访问；
• 左子 7 入栈后，is_solution命中，记录路径[1, 7]；
• 由于没有return，继续深入节点 7 的子树（节点 4、5 及其空子树），这些分支均不满足解条件；
• 递归返回时逐层pop撤销，最终res中只保留唯一解。

因此程序的期望输出为：

[[1, 7]]

亲手验证的方式很简单：在装有 Python 3 的环境下运行上述主源码文件，或在俄罗斯语文档所在目录运行ru/codes/python/chapter_backtracking/preorder_traversal_iii_template.py，即可看到打印的二叉树结构与最终路径列表。仓库为每种主流语言都准备了同构实现，例如 preorder_traversal_iii_template.c、preorder_traversal_iii_template.java、preorder_traversal_iii_template.go、preorder_traversal_iii_template.ts 等，可对照阅读同一框架在不同语言下的写法。

交互式可视化：本仓库的 pythontutor 组织方式

为了便于学习者逐步观察"尝试与回退"的过程，仓库在codes/pythontutor/目录下为每段示例代码保存了对应的 Python Tutor 可视化条目：本文主题对应 codes/pythontutor/chapter_backtracking/preorder_traversal_iii_template.md。本任务的关联文档 ru/codes/pythontutor/chapter_backtracking/preorder_traversal_iii_template.md 即为该文件的俄文版本（简中、繁中、日文版同样存在，见ja/codes/pythontutor/与zh-hant/codes/pythontutor/同名路径）。

这类 md 文件的主体是一条以 URL 编码形式保存了完整可运行 Python 代码的渲染链接：代码内嵌了TreeNode节点类、list_to_tree_dfs/list_to_tree建树工具，以及前面分析的六个框架子函数，并将cumulative、py等查看参数一并编码在链接中，做到"点击即得可逐步执行的可视化代码"。这种组织方式的优点在于：

• 可视化隔离：把 Python Tutor 需要的单文件、可独立执行的代码与其多语言源码分开维护，避免在 URL 中粘贴依赖仓库内部模块的代码；
• 语言对应：每份 pythontutor md 都与 ru/codes/python/ 下的正式源码保持同构，读者可以先看动画理解流程，再回到静态源码精读。

框架映射表：术语到函数的对应关系

为便于把框架代码迁移到其它回溯问题，可将本例题中出现的概念与代码一一对应：

小结

preorder_traversal_iii_template是《Hello 算法》中"回溯算法框架"从理论走向代码的完整示范：它把朴素 DFS 中隐式的"记录、剪枝、恢复"拆成了显式的六个子函数，使回溯的通用骨架可以被显式地复用。理解这段代码后你会发现，N 皇后、全排列、子集和等回溯问题（仓库codes/*/chapter_backtracking/目录下的n_queens、permutations_*、subset_sum_*等文件正是同一章节的姊妹例题）都能装进同一个五步框架中，差异只在于你如何定义state、choices以及那六个子函数——这正是模板化实现最有价值的地方。

【免费下载链接】hello-algo《Hello 算法》：动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語，提供 Python, Java, C++, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo