搞不太清 回溯 vs. 递归 的使用场景
来源：7-4 注意递归的终止条件 Path Sum
大菠萝101
2021-05-04
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回答
-
liuyubobobo
2021-05-05
你的代码的问题是在 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() 的调用。
说实话，这样非常“教条”的语言上的区分，我觉得意义不大。你看到这个问题想到回溯，想到递归，我觉得已经有相当的解决问题的感觉和基础了。你的描述也很到位。对于这样一个问题，你说它是回溯解决，没有问题，你说他是递归解决，也没有问题，你说他是递归搜索解，也没有问题。怎么称呼这个接发的意义没有那么大。我没有见过有人在面试的过程中，要求详细阐述什么是递归，什么是回溯的。
在算法设计上，很多类似的概念是同理的，比如对于动态规划，没有人会让你详细阐述动态规划的三个基本条件是什么意思？也不会有人问你分治和递归是什么关系（通常分治法也需要使用递归实现），等等。我的经验是，不要太纠结这些概念层次的东西。关键还是你能快速找到解决问题的方法（我的经验是，精通概念其实并不能帮你快速找到解决问题的方法），写出正确的代码。如果代码有问题，可以调试出来。
继续加油！：）
00
相似问题