知识卡片
回溯撤销状态再试其他选择
回溯沿一种选择深入,若已穷尽或违反约束,就撤销这次选择对共享状态的修改,回到此前状态继续其他候选。函数返回负责控制流,撤销负责数据状态,二者都可能需要。
路径列表加入节点后,回到父层前应弹出该节点;否则兄弟分支会看到前一路残留。把选择、递归、撤销配对,是复用可变状态而保持各分支独立的核心。
结构图:
flowchart TD
A[选择合法候选] --> B[更新当前状态]
B --> C[递归探索]
C --> D[撤销本次更新]
D --> E[尝试下一候选]
E --> A
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- · 查看原书依据
回退并不仅仅包括函数返回 。为解释这一点,我们对例题一稍作拓展。 例题二 在二叉树中搜索所有值为 的节点,请返回根节点到这些节点的路径 。 在例题一代码的基础上,我们需要借助一个列表path 记录访问过的节点路径。当访问
参考来源
- 位置:《Hello 算法--Go版本》第13章《回溯》(来源项目book-sources:extracted/Hello 算法--Go版本/_epub-src/OEBPS/Text/6.html;spine 5,归一字符[20560,20670))
- 结论依据:实际preOrderII path append/截短及尝试回退解释支持。
- 原始内容:回退并不仅仅包括函数返回 。为解释这一点,我们对例题一稍作拓展。 例题二 在二叉树中搜索所有值为 的节点,请返回根节点到这些节点的路径 。 在例题一代码的基础上,我们需要借助一个列表path 记录访问过的节点路径。当访问