Hello 算法回溯入门实战前序遍历剪枝例题三preorder_traversal_iii_compact逐行拆解【免费下载链接】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 算法》回溯章节的「例题三」展开给定二叉树寻找所有根节点到值为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、右孩子37的左右孩子为4、53的左右孩子为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的实现思路一致。针对本例数组逐下标展开下标值角色01根节点17根节点的左孩子23根节点的右孩子34节点7的左孩子45节点7的右孩子56节点3的左孩子67节点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变化pre_order(1)push 1path[1]1≠7进入左孩子pre_order(7)push 7path[1,7]77→res.append([1,7])进入其左孩子pre_order(4)push 4path[1,7,4]无子节点pop回[1,7]pre_order(5)push 5path[1,7,5]无子节点pop回[1,7]节点7的两个子树搜完pop回path[1]pre_order(3)命中剪枝条件root.val 3直接返回3、6、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_validchoice is not None and choice.val ! 3是否成解内联root.val 7拆成is_solutionstate 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/均提供同步副本。以下是可直接查看的关键实现文件Pythoncodes/python/chapter_backtracking/preorder_traversal_iii_compact.py依赖modules工具包比可视化页面版多出print_tree的树形打印Javacodes/java/chapter_backtracking/preorder_traversal_iii_compact.java使用ListTreeNode静态字段path、resCcodes/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的顺序逐段阅读并在本地运行任一语言实现验证输出观察剪枝分支如何从结果中消失。【免费下载链接】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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
Hello 算法回溯入门实战：前序遍历剪枝例题三（preorder_traversal_iii_compact）逐行拆解
Hello 算法回溯入门实战前序遍历剪枝例题三preorder_traversal_iii_compact逐行拆解【免费下载链接】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 算法》回溯章节的「例题三」展开给定二叉树寻找所有根节点到值为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、右孩子37的左右孩子为4、53的左右孩子为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的实现思路一致。针对本例数组逐下标展开下标值角色01根节点17根节点的左孩子23根节点的右孩子34节点7的左孩子45节点7的右孩子56节点3的左孩子67节点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变化pre_order(1)push 1path[1]1≠7进入左孩子pre_order(7)push 7path[1,7]77→res.append([1,7])进入其左孩子pre_order(4)push 4path[1,7,4]无子节点pop回[1,7]pre_order(5)push 5path[1,7,5]无子节点pop回[1,7]节点7的两个子树搜完pop回path[1]pre_order(3)命中剪枝条件root.val 3直接返回3、6、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_validchoice is not None and choice.val ! 3是否成解内联root.val 7拆成is_solutionstate 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/均提供同步副本。以下是可直接查看的关键实现文件Pythoncodes/python/chapter_backtracking/preorder_traversal_iii_compact.py依赖modules工具包比可视化页面版多出print_tree的树形打印Javacodes/java/chapter_backtracking/preorder_traversal_iii_compact.java使用ListTreeNode静态字段path、resCcodes/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的顺序逐段阅读并在本地运行任一语言实现验证输出观察剪枝分支如何从结果中消失。【免费下载链接】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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考