Leetcode113:路径总和——dfs、回溯

题目

https://leetcode-cn.com/problems/path-sum-ii/

题解

dfs无回溯

我们用深度优先搜索，在搜索时把当前路径记录下来为nums。如果满足

1. sum(nums)==targetSum；
2. 该节点是叶节点；

就记录下这个路径。搜索完成后，我们就能把所有满足条件的路径找出来了。

代码的总体框架就是一个深度优先搜索，在这个框架的基础上修改使其符合题意。这是写代码的思路。下面是自己写的代码：

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
        if not root:
            return []
        res = []
        nums = []
        
        def backtracking(nums, node):
            nums.append(node.val)
            # print(nums)
            if sum(nums)==targetSum and not node.left and not node.right:
                res.append(nums.copy())
            if node.left:
                backtracking(nums.copy(), node.left)
            if node.right:
                backtracking(nums.copy(), node.right)
                
        backtracking(nums, root)
        return res

细节：

• 在往下递归是我传的参数不是nums的引用，而是复制了一个nums传给下一个函数。因此在做每一步递归时都有专属于它的一个nums，所以这段代码没有用到回溯。占用空间也比较大。
• 上面一点很重要！

dfs、回溯

如果把nums.copy()改成nums，然后在backtracking()的末尾加上nums.pop()，就是回溯了。

这样的话，传递的就是nums的引用，所有的递归过程用的都是同一个nums。在每次递归结束，往上回溯的时候通过pop()删去nums中最后一个元素。

class Solution:
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
        if not root:
            return []
        res = []
        nums = []
        def backtracking(nums, node):
            nums.append(node.val)
            # print(nums)
            if sum(nums)==targetSum and not node.left and not node.right:
                res.append(nums.copy())
            if node.left:
                backtracking(nums, node.left)
            if node.right:
                backtracking(nums, node.right)
            nums.pop()
        backtracking(nums, root)

        return res

把这段代码跟Leetcode78题放在一起看，发现都是在合适的位置加一个pop()，这其实是回溯的重要特点。

时间和空间复杂度：不会算…

记录父节点、bfs

还有个很聪明的做法，就是用一个哈希表来每一个节点的父节点。这样，不用记录路径，只记录累加和。每找到一个满足条件的叶节点，就从该节点出发向父节点迭代，还原路径。

代码在官方题解～