这里指的是这个leetcode问题。https:/leetcode.comroblemspath-sum-iii。
基本上，我得到一棵二进制树，其中每个节点包含一个整数值。我必须找到与给定值相加的路径数。
在这里建立一个示例树
class TreeNode:
def __init__(self, val, left=None, right=None):
self.val = val
self.left = left
self.right = right
root = TreeNode(12)
root.left = TreeNode(7)
root.right = TreeNode(1)
root.left.left = TreeNode(4)
root.right.left = TreeNode(10)
root.right.right = TreeNode(5)
这是我使用递归的解决方案
def count_paths(root, S):
cache = {0:1}
def helper(node, S:int, curr_path:int, cache:dict, result:int):
if not node:
return result
curr_path += node.val
prev_path = curr_path - S
result += cache.get(prev_path, 0)
cache[curr_path] = cache.get(curr_path, 0) + 1
my_node = None
if node != None:
my_node = node.val
print("node: {}, curr: {}, prev: {}".format(my_node, curr_path, prev_path))
print(cache)
print(result)
helper(node.left, S, curr_path, cache, result)
helper(node.right, S, curr_path, cache, result)
return result
return helper(root, S, 0, cache, 0)
基本上我不明白为什么递归函数不更新我的 结果 变量，但它更新了我的 缓存 变量。
有没有一种正确的方法来更新结果变量？
这是测试用例
count_paths(root, 11)
我打印了每一行的结果
node: 12, curr: 12, prev: 1
{0: 1, 12: 1}
0
node: 7, curr: 19, prev: 8
{0: 1, 12: 1, 19: 1}
0
node: 4, curr: 23, prev: 12
{0: 1, 12: 1, 19: 1, 23: 1}
1
node: 1, curr: 13, prev: 2
{0: 1, 12: 1, 19: 1, 23: 1, 13: 1}
0
node: 10, curr: 23, prev: 12
{0: 1, 12: 1, 19: 1, 23: 2, 13: 1}
1
node: 5, curr: 18, prev: 7
{0: 1, 12: 1, 19: 1, 23: 2, 13: 1, 18: 1}
0
Tree has paths: 0
谁能解释一下我在这里遗漏了什么？我感觉我在这里犯了一个基本的递归错误。我知道我做了一个类，然后把变量存储在那里，但我真的不明白如何正确地进行递归。非常感谢!
tldr。
Python 默认是通过引用传递的，但由于整数是不可变的，所以就像通过复制传递一样。这里最简单的变通方法是类似于 result += helper(...), or result = helper(...).
答案很长。
在许多语言中(如C++和Java)，传递参数默认为传递这些对象的副本。如果你想把一个对象传递到一个函数中，并让它在函数的上下文之外更新使用，你必须传递一个指针 (或类似的东西)。
另一方面，Python 默认是通过引用来传递。这将使你认为你的 result 变量会在原地更新，对吗？
问题是 result，作为一个整数，是不可改变的。所以，当你在一个递归调用中改变它的值时，它不会改变 result 变量的其他调用。它只是将标签重新分配给 result 到一个新的整数值。但只在该函数调用的范围内。 一旦函数返回，新值就会丢失。
如果你想通过函数调用更新一个整数变量的值，你必须将变量设置为函数的返回值（见上面的tldr），或者将整数包在一个可变对象中（见 在Python中通过引用传递一个整数).