递归更新变量

Question

这里指的是这个 leetcode 问题：https://leetcode.com/problems/path-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)

基本上我不明白为什么递归函数不更新我的 result 变量而是更新我的 cache 变量。

是否有更新结果变量的正确方法？

这是测试用例

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

有人可以解释一下我在这里缺少什么吗？我觉得我在这里犯了一个基本的递归错误。我知道我做了一个 class 并只是将变量存储在那里，但我真的发现了解如何正确地进行递归。非常感谢！

Answer 1

tldr:

Python 默认通过引用传递，但由于整数是不可变的，所以它们就像通过复制传递一样。这里最简单的解决方法是 result += helper(...), or result = helper(...).

长答案：

在许多语言中（如 C++ 和 Java），传递参数默认为传递这些对象的副本。如果你想将一个对象传递给一个函数并更新它以便在该函数的上下文之外使用，你必须传递一个指针（或类似的东西）。

另一方面，

Python 默认通过引用传递。这会让您认为您的 result 变量会就地更新，对吗？

问题是 result 作为一个整数，是不可变的。因此，当您在其中一个递归调用中更改其值时，它不会更改其他调用的 result 变量。它只是将标签 result 重新分配给一个新的整数值， 但仅在该函数调用的范围内。 一旦函数 returns，新值就会丢失。

如果你想用函数调用更新整数变量的值，你必须将变量设置为函数的 return 值（参见上面的 tldr），或者将整数包装在可变变量中对象（参见 Passing an integer by reference in Python）。

递归更新变量

Updating variables in recursion

python

tree

recursion

breadth-first-search

binary-search-tree