Hello 算法回溯入门实战：前序遍历剪枝例题三（preorder_traversal_iii_compact）逐行拆解

本文围绕《Hello 算法》回溯章节的「例题三」展开：给定二叉树，寻找所有根节点到值为 7 的节点路径，并要求路径不得经过值为 3 的节点。文章以 preorder_traversal_iii_compact 可视化页面中的完整代码为主体，结合仓库内 Python、Java、C++ 等多语言实现与配套文档 backtracking_algorithm.md，逐行剖析"尝试—回退—剪枝"三段式写法，帮助你掌握用前序 DFS 解决带约束的树路径搜索问题，并理解它与框架版回溯实现的差异。读完本文，你将能独立分析并手写此类"DFS + 状态回溯 + 约束剪枝"的代码。

例题三到底在求什么

在正式读代码前，先明确问题本身。教材中例题三的表述是：

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

相比同一章节内的前两个例题，约束逐级加强：

例题	目标	是否记录路径	是否带约束
例题一	找出所有值为 7 的节点	否，只记录节点值	无
例题二	找出根到 7 的路径	是，借助 path 列表	无
例题三	找出根到 7 且不含 3 的路径	是，借助 path 列表	路径不得包含值 3 的节点

例题三与例题二的核心差异只有一个：多了一条约束条件，而约束条件通常可以转化为"剪枝"——遇到值为 3 的节点立刻终止该分支的搜索，不再向下递归。

测试用的二叉树由数组 [1, 7, 3, 4, 5, 6, 7] 按层序构建（见下文"数组如何还原成树"），其结构为：根节点 1，左孩子 7、右孩子 3；7 的左右孩子为 4、5；3 的左右孩子为 6、7。直观上，值为 7 的节点有两个（根节点的左孩子，以及 3 的右孩子），但由于 3 会被剪枝，最终只应输出一条合法路径 [1, 7]。

代码全貌：单文件自包含实现

preorder_traversal_iii_compact.md 在构建时由源码片段自动嵌入（页首注释 [file]{preorder_traversal_iii_compact}-[class]{}-[func]{pre_order} 即标记了这一对应关系），其中的代码是一个"开箱即用"的单文件 Python 程序——它不依赖仓库的 modules 工具包，而是内联了 TreeNode 类和数组反序列化函数，因此可以被逐行可视化执行。完整代码如下（注释为便于阅读进行了翻译）：

class TreeNode:
    """二叉树节点类"""

    def __init__(self, val: int = 0):
        self.val: int = val              # 节点值
        self.left: TreeNode | None = None  # 左子节点引用
        self.right: TreeNode | None = None # 右子节点引用


def list_to_tree_dfs(arr: list[int], i: int) -> TreeNode | None:
    """将列表反序列化为二叉树：递归"""
    # 索引越界或对应元素为 None 时，返回 None
    if i < 0 or i >= len(arr) or arr[i] is None:
        return None
    # 构建当前节点
    root = TreeNode(arr[i])
    # 递归构建左右子树
    root.left = list_to_tree_dfs(arr, 2 * i + 1)
    root.right = list_to_tree_dfs(arr, 2 * i + 2)
    return root


def list_to_tree(arr: list[int]) -> TreeNode | None:
    """将列表反序列化为二叉树"""
    return list_to_tree_dfs(arr, 0)


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 __name__ == "__main__":
    root = list_to_tree([1, 7, 3, 4, 5, 6, 7])

    # 前序遍历
    path = list[TreeNode]()
    res = list[list[TreeNode]]()
    pre_order(root)

    print("\n输出所有根节点到节点 7 的路径，路径中不包含值为 3 的节点")
    for path in res:
        print([node.val for node in path])

数组如何还原成树：list_to_tree 的反序列化原理

pre_order 只是搜索部分，在此之前，还需要把测试数据 [1, 7, 3, 4, 5, 6, 7] 还原成一棵真正的二叉树。这依赖 list_to_tree_dfs 用到的层序下标关系：

• 对数组中下标为 i 的元素，它的左孩子在 2 * i + 1，右孩子在 2 * i + 2；
• 当 i 越界，或 arr[i] 本身是 None（表示空位）时，递归返回 None。

list_to_tree 只是从 i = 0 这个根下标启动递归的入口。这种"线性数组 ↔ 完全二叉树"的映射是《Hello 算法》二叉树数组表示一节的基础概念，也是堆（my_heap）等结构使用下标寻址的前提，与仓库中 modules 的 tree_node.py 里 list_to_tree 的实现思路一致。

针对本例数组逐下标展开：

下标	值	角色
0	1	根节点
1	7	根节点的左孩子
2	3	根节点的右孩子
3	4	节点 7 的左孩子
4	5	节点 7 的右孩子
5	6	节点 3 的左孩子
6	7	节点 3 的右孩子

pre_order 的四段式解剖：剪枝、尝试、记录、回退

pre_order 将"回溯 = 尝试 + 回退"以及"约束 = 剪枝"浓缩在 8 行代码里，每一段都对应回溯算法的核心概念：

1. 剪枝（第一段）

if root is None or root.val == 3:
    return

前序遍历到了 None（越过叶节点）或值恰好为 3 的节点，直接 return，整个子树被"剪掉"。这正是教材中例题三相对例题二新增的一行：它在路径上的值进入 3 之前就中断了搜索，因此 3 的整棵子树（含 6、7 两个节点）都不会产生任何解。参考文档 backtracking_algorithm.md#剪枝 的表述："遇到值为 3 的节点则提前返回，不再继续搜索"，剪枝避免了许多无意义的尝试。

2. 尝试（第二段）

path.append(root)

把当前节点压入路径 path，这是"做出选择、更新状态"。在例题一（preorder_traversal_i_compact.py）中只记录节点本身，而例题二、三用 path 承载"当前已访问的节点路径"这一状态。

3. 记录解（第三段）

if root.val == 7:
    res.append(list(path))

每当当前节点值等于 7，就把 path 的拷贝追加进结果集。注意 list(path) 是浅拷贝——如果直接 res.append(path)，后续 path.pop() 会反向污染已记录的解，这是写路径类回溯最容易踩的坑。

4. 回退（第四段）

pre_order(root.left)
pre_order(root.right)
path.pop()

先深搜左右子树，子树全部遍历完毕后，执行 path.pop() 把当前节点移出路径，恢复到进入本节点之前的状态，以便父节点去尝试另一条分支。"尝试"与"回退"互为逆向操作，与教材中给出的概念一一对应（可对照 backtracking_algorithm.md 的术语表：状态 = path、尝试 = 递归进入子节点并压栈、回退 = 越过叶节点或约束节点后的函数返回与弹栈）。

手工推演一遍完整执行轨迹

对照上一节树结构，模拟 pre_order 的执行（用 push/pop 表示 path 变化）：

1. pre_order(1)：push 1，path=[1]，1≠7，进入左孩子；
2. pre_order(7)：push 7，path=[1,7]，7==7 → res.append([1,7])，进入其左孩子；
3. pre_order(4)：push 4，path=[1,7,4]，无子节点，pop 回 [1,7]；
4. pre_order(5)：push 5，path=[1,7,5]，无子节点，pop 回 [1,7]；
5. 节点 7 的两个子树搜完，pop 回 path=[1]；
6. pre_order(3)：命中剪枝条件 root.val == 3，直接返回，3、6、7 所在的整条分支不再展开；
7. 根节点的子树搜完，pop 回 path=[]。

最终 res = [[1, 7]]，程序输出恰为：

[1, 7]

值得说明：下标 6 处还有一个值为 7 的节点，但它的父节点 3 已被剪枝，因此该候选路径 [1, 3, 7] 永远不会被尝试——这正是"约束条件通过剪枝减少了搜索空间"的直观体现。

剪枝在做什么：少搜一条子树

本例中剪枝省掉的是一次规模很小的分支（节点 3 及其两个孩子），直观收益不明显；但概念本身意义重大：剪枝发生在"选择进入某分支之前"，而非"进入之后才发现不合法"。当约束条件能在树的较深层命中时，被剪掉的往往是整棵指数级规模的子树。把本例的剪枝条件换成"路径中不得包含偶数节点"等更强约束，收益会急剧放大。因此教材把剪枝列为回溯性能优化的第一手段，详见 backtracking_algorithm.md 的优点与局限性："剪枝：避免搜索那些肯定不会产生解的路径，从而节省时间和空间。"

compact 版与框架版（template）的对比

"compact"（紧凑版）的命名是相对于框架版 preorder_traversal_iii_template 而言的。两者解决完全相同的例题三，输出也一致，但组织方式不同：

关注点	compact 版（本文）	template 版
剪枝判断	内联在 pre_order 开头的 if 中	拆成独立函数 is_valid（choice is not None and choice.val != 3）
是否成解	内联 root.val == 7	拆成 is_solution（state and state[-1].val == 7）
状态更新	直接 path.append / path.pop	抽象为 make_choice / undo_choice
通用性	针对本题定制，代码最短	匹配"回溯算法框架"，可迁移到全排列、子集和、n 皇后等问题

框架版把回溯过程统一为 is_solution → record_solution → is_valid → make_choice → backtrack → undo_choice 六步（见 backtracking_algorithm.md 的框架代码）。compact 版把这几步压进一个递归函数，代码紧凑但"术语边界"模糊；template 版虽然冗长，但读者能清晰看到每一步对应哪个回溯概念。教材的安排是有意为之：先用 compact 版把"尝试、回退、剪枝"讲透，再用框架版证明同一问题可以套用统一模板，从而引出全排列（permutations_i.py）、子集和（subset_sum_i.py）、n 皇后（n_queens.py）等后续经典问题。

框架版代码中还隐藏着一个容易被忽略的细节：它在 record_solution 之后不返回，而是继续遍历左右子节点，目的是让 DFS 在找到节点 7 之后继续向更深层搜索——这一点与 compact 版行为一致（compact 版在 val == 7 时仅记录，并不 return），但需要框架版显式省略 return 语句才能保持，否则会在第一个解处提前终止整轮搜索（见配套文档中的对比图 backtrack_remove_return_or_not.png）。

多语言实现与运行验证

同一例题在仓库中按语言各有一份等价实现，主目录与 en/、ja/、zh-hant/、ru/ 均提供同步副本。以下是可直接查看的关键实现文件：

• Python：codes/python/chapter_backtracking/preorder_traversal_iii_compact.py（依赖 modules 工具包，比可视化页面版多出 print_tree 的树形打印）
• Java：codes/java/chapter_backtracking/preorder_traversal_iii_compact.java（使用 List<TreeNode> 静态字段 path、res）
• C++：codes/cpp/chapter_backtracking/preorder_traversal_iii_compact.cpp
• 其他语言：C、C#、Go、JavaScript、TypeScript、Dart、Kotlin、Ruby、Rust、Swift 均位于各自语言的 chapter_backtracking/preorder_traversal_iii_compact.* 路径下

Python 版可直接运行验证输出。在仓库根目录下执行：

python3 codes/python/chapter_backtracking/preorder_traversal_iii_compact.py

控制台会先打印初始化后的二叉树结构（print_tree），随后输出结果 [1, 7]。若要体验可视化逐步执行，可打开 ja/codes/pythontutor/chapter_backtracking/preorder_traversal_iii_compact.md 中内嵌的 PythonTutor 页面，以步进方式观察 path 的压栈与弹栈过程——这正是该文档文件在《Hello 算法》"一键运行"学习链路中的定位。

小结

例题三的 compact 版代码虽然只有十余行，却浓缩了回溯算法三个最核心的动作：遇到约束节点（值 3）剪枝、压入节点尝试、弹出节点回退。读懂它，你便掌握了"带约束的 DFS 路径搜索"这一通用模式；再对照框架版体会术语抽象，就能平滑过渡到更复杂的回溯问题。建议按"数组反序列化 → 剪枝条件 → 记录解时拷贝 path → 递归后 pop"的顺序逐段阅读，并在本地运行任一语言实现验证输出，观察剪枝分支如何从结果中消失。