本文共 1424 字，大约阅读时间需要 4 分钟。

本系列文章为《剑指Offer》刷题笔记。

刷题平台：

回溯法按 深度优先策略 搜索问题的解空间树。

.

首先从根节点出发搜索解空间树，当算法搜索至解空间树的某一节点时，先利用剪枝函数判断该节点是否可行（即能得到问题的解）。

.

如果不可行，则跳过对该节点为根的子树的搜索，逐层向其祖先节点回溯；否则，进入该子树，继续按深度优先策略搜索。

解题图示

1. 当完成第一颗子树（根 到 叶子节点）的遍历，变量值如下图所示
   
   在7节点 的这一轮，得到 tar = -5, 无root.left，也无root.right，就把7 pop出去（从path列表中删去）
2. 如果不可行，则跳过对该节点为根的子树的搜索，逐层向其祖先节点回溯
   ！然后回溯到第三层，节点11的左子树7搜索完毕，到了右子树2。
   满足以下条件：
   ①它是叶子节点；
   ②该路径path总和等于 目标值
   则把该路径path 加入res 列表中
   
3. [5, 8, 13] 不满足条件
   [5, 8, 4, 5] 满足条件，则把该路径path 加入res 列表中
   [5, 8, 4, 1] 不满足条件
   
   

class TreeNode:    def __init__(self, x):        self.val = x        self.left = None        self.right = Noneclass Solution:    # 返回二维列表，内部每个列表表示找到的路径    def pathSum(self, root, sum):        res, path = [], []        def recur(root, tar):            if not root: return            path.append(root.val)            tar -= root.val            if tar == 0 and not root.left and not root.right:                res.append(list(path))                            recur(root.left, tar)            recur(root.right, tar)            path.pop()        recur(root, sum)        return res

注：

https://leetcode-cn.com/leetbook/read/illustration-of-algorithm/5dc8rr/

https://blog.csdn.net/jarvischu/article/details/16067319