搞不太清 回溯 vs. 递归 的使用场景

Question

bobo老师您好~

对于力扣 113. Path Sum II, 用递归的方法可以做出这道题. 但是在刚看到这道题时, 脑子里最开始的思路就是用回溯算法, 比如 Example 1中, 如果走到7, 发现不对, 就回溯到上面一个节点然后看上个节点的右节点 - 看起来是一个回溯思路.
但是当我用回溯算法写的时候总是不对, 能不能请bobo老师帮忙看一下呢?
代码:

# 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: TreeNode, targetSum: int) -> List[List[int]]:
        res, path = [], []
        
        def backtrack(root, target): 
            if not root: 
                return 
            if not root.left and not root.right: 
                if root.val == target: 
                    path.append(root.val)
                    res.append(path[:])
                return
            
            path.append(root.val)
            backtrack(root.left, target - root.val)
            path.pop()
            
            path.append(root.val)
            backtrack(root.right, target - root.val)
            path.pop()
        
        backtrack(root, targetSum)
        return res

结果:
Output
[[5,4,11,2],[5,5,8,4,5]]
Expected
[[5,4,11,2],[5,8,4,5]]

请问老师:

1. 我上面代码逻辑有什么问题呢?
2. 我知道回溯算法底层就是递归, 但是请问什么时候用回溯, 什么时候用单纯的递归?

Answer 1

liuyubobobo 2021-05-05 14:46:46

你的代码的问题是在 if root.val == target 的时候，没有 pop()

以下代码可以 ac：(注意注释的地方)

class Solution:
    def pathSum(self, root: TreeNode, targetSum: int) -> List[List[int]]:
        res, path = [], []
        
        def backtrack(root, target): 
            if not root: 
                return 
            if not root.left and not root.right: 
                if root.val == target: 
                    path.append(root.val)
                    res.append(path[:])
                    path.pop() // 这里要 pop !!!
                return
            
            path.append(root.val)
            backtrack(root.left, target - root.val)
            path.pop()
            
            path.append(root.val)
            backtrack(root.right, target - root.val)
            path.pop()
        
        backtrack(root, targetSum)
        return res

整体来说，递归和回溯并不是冲突的。回溯一定要靠递归实现。如归非要说他们的区别，回溯是一种算法思想，通常用于非线性结构的暴力搜索（比如这个问题），而递归是一种逻辑组织的方式（和循环一样）。但是，递归一定有“回”的过程，因为一个递归函数执行完毕，一定会回到上层调用的递归函数中。但通常回溯会有显式的，将当前搜索的解“退回”的动作，在这个问题中，就表现在 path.pop() 的调用。

说实话，这样非常“教条”的语言上的区分，我觉得意义不大。你看到这个问题想到回溯，想到递归，我觉得已经有相当的解决问题的感觉和基础了。你的描述也很到位。对于这样一个问题，你说它是回溯解决，没有问题，你说他是递归解决，也没有问题，你说他是递归搜索解，也没有问题。怎么称呼这个接发的意义没有那么大。我没有见过有人在面试的过程中，要求详细阐述什么是递归，什么是回溯的。

在算法设计上，很多类似的概念是同理的，比如对于动态规划，没有人会让你详细阐述动态规划的三个基本条件是什么意思？也不会有人问你分治和递归是什么关系（通常分治法也需要使用递归实现），等等。我的经验是，不要太纠结这些概念层次的东西。关键还是你能快速找到解决问题的方法（我的经验是，精通概念其实并不能帮你快速找到解决问题的方法），写出正确的代码。如果代码有问题，可以调试出来。

继续加油！：）