Hello 算法：前序遍历加剪枝的二叉树约束路径回溯（Python 源码精讲）

本篇基于《Hello 算法》俄语版配套动画脚本 preorder_traversal_iii_compact.md 展开，完整拆解回溯算法章节“例题三”的核心问题：在二叉树中找出所有“从根节点到值为 7 的节点”的路径，且路径中不允许出现值为 3 的节点。读完本文，你可以掌握用**前序遍历 + 路径记录 + 剪枝（pruning）+ 回退（undo）**四要素构建约束搜索问题的完整方法，并能对照仓库源码理解每一步在 Python 中的具体实现。

问题定义：带约束的路径查找

回溯章节中给出了三个递进的二叉树问题（见 ru/docs/chapter_backtracking/backtracking_algorithm.md）：

1. 找出树中所有值为 7 的节点（纯遍历）；
2. 返回根节点到这些节点的路径（引入 path 路径记录）；
3. 在返回路径的基础上增加约束：路径中不能包含值为 3 的节点（引入剪枝）——本文的主角。

第三个问题的关键点在于“约束”：如果某条分支上出现了值为 3 的节点，那么这条分支上的所有路径都必然非法，此时应立即终止该分支的探索，不再递归下去。俄语版文档将其表述为“отсечение”（剪枝），即“遇到值为 3 的节点立刻返回，不再继续深入”。

对应的可运行源码为仓库中的 codes/python/chapter_backtracking/preorder_traversal_iii_compact.py，本文分析的核心函数 pre_order 与该动画脚本中的实现完全一致。

输入构造：用列表表示二叉树

约束路径问题需要一个具体的树。示例使用列表 [1, 7, 3, 4, 5, 6, 7] 按数组表示法（完全二叉树的索引规则）反序列化为二叉树：节点 i 的左子节点在索引 2*i+1，右子节点在索引 2*i+2。

动画脚本是自包含的（不依赖外部模块），内嵌了 TreeNode 与 list_to_tree 两个辅助部分，其核心逻辑与仓库工具库 codes/python/modules/tree_node.py 中的 list_to_tree_dfs 相同：

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)

对输入 [1, 7, 3, 4, 5, 6, 7]，得到的树结构为：

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

注意右子树中的 3 正是“陷阱”：它的子节点 7（索引 6）本身是合法目标，但由于祖先含 3，通往它的路径必须被整体剪掉。

核心算法：pre_order 的四段式结构

下面是动画脚本中解码后的主函数 pre_order，它与仓库实现逐行等价：

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()

这段不到 10 行的递归函数完整体现了回溯算法的三个基本动作：

1. 剪枝（Pruning）：入口处先排除非法分支

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

函数第一行同时处理两种终止条件：空节点（正常遍历边界）与值为 3 的节点（约束违反）。俄语版文档特别强调：剪枝“非常直观——把不满足约束的分支直接砍掉，避免大量无意义的尝试，从而提高搜索效率”。从源码结构看，将剪枝放在进入函数时而不是递归调用前，使得每一层递归都天然安全，父、子、孙节点的值都不会被重复检查。

2. 尝试（Try）：把当前节点加入路径

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

path 是一个全局（闭包外定义）列表，始终表示“从根到当前节点的已探索路径”。关键点在于 res.append(list(path))：必须用 list(path) 拷贝一份快照再存入结果，因为 path 对象本身会在后续递归中被不断修改（append/pop），若直接 res.append(path)，所有记录最终都会指向同一份被清空后的列表。

3. 回退（Undo）：递归返回前撤销选择

pre_order(root.left)
pre_order(root.right)
# 回退
path.pop()

左、右子树探索完成后，当前节点已不再属于“当前路径”，必须 pop() 恢复原状。这一步保证了：当函数返回到父节点并转而探索另一棵子树时，path 中不会残留来自兄弟分支的节点。尝试与回退成对出现，是路径类回溯问题不出错的前提。

完整可运行脚本与运行结果

俄语版动画脚本将 TreeNode、list_to_tree、pre_order 与驱动代码合并为单文件（注释为俄语，算法逻辑与仓库版本一致）。仓库中对应的可执行版本 preorder_traversal_iii_compact.py 的驱动部分为：

if __name__ == "__main__":
    root = list_to_tree([1, 7, 3, 4, 5, 6, 7])
    print("\n初始化二叉树")
    print_tree(root)

    # 前序遍历
    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])

其中 TreeNode、list_to_tree、print_tree 均从仓库公共模块 codes/python/modules/init.py 统一导入。执行该脚本的输出为：

初始化二叉树
          1
        /   \
       7     3
      / \   / \
     4   5 6   7

输出所有根节点到节点 7 的路径，路径中不包含值为 3 的节点
[1, 7]

可以手动验证这条结果：树中共有两个值为 7 的目标节点——左子节点 7 和右子树的 7。前者路径 [1, 7] 合法；后者路径为 1 -> 3 -> 7，含值为 3 的祖先节点，被剪枝拦截。因此最终解集恰为 [1, 7] 一条。

执行过程逐步跟踪

以树的右子树为例跟踪剪枝如何生效：

1. pre_order(1)：path=[1]，递归进入左子树 7；
2. pre_order(7)：path=[1,7]，命中 root.val == 7，记录 [1,7]；继续递归其左子 4、右子 5（均非 7，探索后回退）；返回前 pop，path 恢复为 [1]；
3. pre_order(3)：入口处即因 root.val == 3 直接 return——其子树 6、7 完全未被访问；
4. 回到 pre_order(1)，pop 后 path 清空，搜索结束。

第 3 步正是剪枝的价值体现：目标节点 7（索引 6）虽然存在，但算法根本没有“看到”它。

与通用回溯框架的对照

同一问题在仓库中还提供了一个通用框架版本 codes/python/chapter_backtracking/preorder_traversal_iii_template.py，它把“剪枝 / 尝试 / 回退”抽象为五个可替换的回调：

def is_valid(state, choice):            # 剪枝：判断选择是否合法
    return choice is not None and choice.val != 3

def make_choice(state, choice):         # 尝试：更新状态
    state.append(choice)

def undo_choice(state, choice):         # 回退：恢复状态
    state.pop()

def backtrack(state, choices, res):
    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)  # 回退

对照两种写法可以看到，紧凑版 pre_order 中每个语句都能一一对应到框架里的抽象角色：root.val == 3 的判断对应 is_valid 的合法性检查，path.append/pop 对应 make_choice/undo_choice。俄语版文档也指出：紧凑版更贴近树形结构、写法更短，而框架版“更通用——许多回溯任务都可以在这个框架内解决，只需针对具体问题定义 state 和 choices”。理解紧凑版后再看框架版，二者互为印证。

复杂度分析

设树中节点总数为 N：

• 时间复杂度：最坏情况下（无节点被剪掉）访问全部 N 个节点，每个节点仅常数次操作，为 O(N)；剪枝只会减少访问的节点数，因此 O(N) 是上界。结果记录本身的开销为“解的总长度”，在本示例中可忽略；
• 空间复杂度：递归调用栈深度为树高，最坏（链状树）为 O(N)；path 列表同样最深 O(N)，不重复计入则为 O(树高)；

从源码结构看，该实现没有使用显式栈模拟遍历，直接依赖 Python 递归；对于极深的树，需注意 Python 默认递归深度限制这一适用前提。

小结与延伸阅读

本文围绕俄语版动画脚本 ru/codes/pythontutor/chapter_backtracking/preorder_traversal_iii_compact.md 所对应的“例题三”，完整给出了带约束路径查找的 Python 实现：

• 问题：找所有根到值为 7 节点的路径，且路径不含值为 3 的节点；
• 方法：前序遍历 + path 路径快照 + 入口剪枝 + 返回前回退；
• 关键细节：记录解时必须 list(path) 拷贝；尝试与回退必须成对出现；剪枝前置于递归，保证子树整体不被误访问。

仓库内可直接对照的完整资源：

资源	路径
本例可运行源码（Python）	codes/python/chapter_backtracking/preorder_traversal_iii_compact.py
通用回溯框架版实现	codes/python/chapter_backtracking/preorder_traversal_iii_template.py
前两级递进问题（例题一、二）	preorder_traversal_i_compact.py、preorder_traversal_ii_compact.py
树节点与序列化工具	codes/python/modules/tree_node.py
回溯章节正文（含剪枝图示）	ru/docs/chapter_backtracking/backtracking_algorithm.md
俄语版逐帧动画脚本（本文对应文档）	ru/codes/pythontutor/chapter_backtracking/preorder_traversal_iii_compact.md

掌握本例后，可继续沿 backtracking_algorithm.md 中“状态—选择—解”的框架，迁移到同目录下的子集和、全排列、N 皇后等更复杂的回溯问题。