有没有更好的方法退出递归？

Question

我有这个功能：

class Solution:
def __init__(self):
        self.flag = False


def hasPathSum(self, root: TreeNode, targetSum: int) -> bool:
    curr_sum = 0            

    
    def dfs(root, curr_sum, target_sum=targetSum):
        if self.flag == True:
            return True
        if root == None:
            return 0
        print(root.val)
        curr_sum += root.val
        print(curr_sum)
        if curr_sum == target_sum:
            self.flag = True
        dfs(root.left, curr_sum)
        dfs(root.right, curr_sum)
    dfs(root, curr_sum, targetSum)
    if self.flag == True:
        return True
    return False

当树的根到叶路径总和等于target_sum时，我想结束递归并得到True。我设法通过添加 dunder 方法 init 并将那里的标志设置为 False 来做到这一点，我在满足要求时切换它。但是在我看来感觉有点不干净也不漂亮。我应该如何以更干净的方式进行？

Answer 1

无论是否达到当前总和，您都可以只使用 dfs 函数 return。这是我正在谈论的一些示例代码：

def hasPathSum(self, root: TreeNode, targetSum: int) -> bool:
    curr_sum = 0            

    
    def dfs(root, curr_sum, target_sum=targetSum):
        if root == None:
            return 0
        print(root.val)
        curr_sum += root.val
        print(curr_sum)
        if curr_sum == target_sum:
            return = True
        return dfs(root.left, curr_sum) or dfs(root.right, curr_sum)
    return dfs(root, curr_sum, targetSum)

Answer 2

你根本不需要 Solution class（强制一切都成为 class 是你不需要的 Java 主义Python 代码），并且您的函数应该 return 它的值而不是将其粘贴在外部变量中。

递归函数的一般模式是：

检查基本情况，return如果满足立即解决
否则，return 使用修改后的参数再次调用该函数的结果使您更接近基本情况。

def has_path_sum(self, root: TreeNode, target_sum: int) -> bool:
    """Returns whether any path through the tree 
    has values that sum to *exactly* target_sum."""
    def dfs(node: TreeNode, curr_sum: int) -> bool:
        """DFS helper that tracks sum of all nodes traversed."""
        # Base case: return False if we run out of nodes.
        if node is None:
            return False
        curr_sum += node.val
        return (
            # Base case: return True if we hit the target sum.
            curr_sum == target_sum
            # Otherwise, recurse into left and right subtrees.
            or dfs(node.left, curr_sum)
            or dfs(node.right, curr_sum)
        )

    return dfs(root, 0)

注意在 DFS 助手的最后部分使用 or——一旦其中一个子句为 True（按顺序），or 立即 returns，所以这个：

        return (
            # Base case: return True if we hit the target sum.
            curr_sum == target_sum
            # Otherwise, recurse into left and right subtrees.
            or dfs(node.left, curr_sum)
            or dfs(node.right, curr_sum)
        )

只是nicer/shorter的一种表达方式：

        # Base case: return True if we hit the target sum.
        if curr_sum == target_sum:
            return  True
        # Otherwise, recurse into left and right subtrees.
        elif dfs(node.left, curr_sum):
            return True
        elif dfs(node.right, curr_sum):
            return True
        else:
            return False

有没有更好的方法退出递归？

is there a better way to exit the recursion?

python

recursion

binary-tree

depth-first-search