基础算法：回溯

回溯

什么是回溯

通常来说，我们会这样介绍回溯算法：回溯法采用试错的思想，它尝试分步地解决一个问题。在分布解决问题的过程中，当它通过尝试发现现有的分步答案不能得到有效地正确的解答的时候，它将取消上一步甚至上几步的计算，再通过其他的可能的分步解答再次尝试寻找问题的答案。回溯法通常用最简单的递归方法来实现，它通过反复地重复上述的步骤来解决问题。回溯算法通常采用“深度优先搜索”来遍历解空间。在“二叉树”章节中，我们提到前序、中序和后序遍历都属于深度优先搜索。接下来，我们利用前序遍历构造一个回溯问题，逐步了解回溯算法的工作原理。

给定一棵二叉树，搜索并记录所有值为7的节点，请返回节点列表。

def pre_order(root: TreeNode):
    """前序遍历：例题一"""
    if root is None:
        return
    if root.val == 7:
        # 记录解
        res.append(root)
    pre_order(root.left)
    pre_order(root.right)

尝试与回退

之所以被称为回溯算法，是因为该算法在探索解空间时会采用“尝试”与“回退”的策略，通过撤销上一步的选择，退回到之前的状态，它得以访问其他的选择。

在二叉树中搜索所有值为7的节点，请返回根节点到这些节点的路径