有更好的方法退出递归吗

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函数返回是否达到当前总和。以下是我所说的一些示例代码：

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类(强制所有东西都是类是Python代码中不需要的Java主义)，您的函数应该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——一旦or的任何一个子句为True(按顺序)，它就会立即返回，因此：

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)
)

只是一种更好/更短的说法：

# 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