python - 我们什么时候应该在递归中添加 return

Question

美好的一天。请问递归什么时候用return？ 我基本上想使用递归来解决以下问题:

给定一棵二叉树的根和一个整数 targetSum，返回所有根到叶的路径，其中路径中节点值的总和等于 targetSum。每条路径都应作为节点值列表返回，而不是节点引用。 根到叶路径是从根开始到任何叶节点结束的路径。叶子是没有 child 的节点。 输入:root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22

输出:[[5,4,11,2],[5,8,4,5]]

解释:有两条路径的总和等于targetSum:

5 + 4 + 11 + 2 = 22

5 + 8 + 4 + 5 = 22

这是我的代码解决方案

def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
        res = []
        def helper(node, target, cur):
            if not node:
                return
            cur.append(node.val)
            if target == node.val and not node.left and not node.right:
                res.append(list(cur))
                print(res)
                return # why can't we put return here
            helper(node.left, target - node.val, cur)
            helper(node.right, target- node.val, cur)
            cur.pop()
        helper(root, targetSum, [])
        return res

我想当我们找到一个解决方案时，我们可以停下来返回资源。 但它会给我一个奇怪的输出。有人可以教我为什么我们不能把 return 放在这里。如有任何建议，我们将不胜感激。

Answer 1

此代码使用回溯方法找到问题的所有解决方案(路径)。

当您提早返回时，您就剥夺了解决方案pop 添加到当前列表的最后一个元素的机会。删除早期返回并让算法负责在基本情况下返回，返回递归堆栈并弹出当前路径中的最后一个元素，如下所示:

def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
        res = []
        def helper(node, target, cur):
            if not node:
                return
            cur.append(node.val)
            if target == node.val and not node.left and not node.right:
                res.append(list(cur))
                print(res)
                # when your code comes out of this if condition
                # node.left and node.right will be None
                # it calls the below functions and they return
                # and then it will pop the last element
            helper(node.left, target - node.val, cur)
            helper(node.right, target- node.val, cur)
            cur.pop()
        helper(root, targetSum, [])
        return res