python - 如何通过Python中的递归函数携带变量？

Question

我在做一些 leetcode 问题，发现我不能像我想的那样通过递归函数携带我的变量。

例如，假设我想对树的所有节点求和。

所以我想以这种方式实现它：

def Sum(root):


    def dfs(root,x):
        if root:
            dfs(root.left, x)
            x.append(root.val)
            dfs(root.right,x)

        return x

    return(sum(dfs(root,x=[])))

这有效。但是，假设我想减少内存，为什么这个实现不起作用，只是返回根节点。

def Sum(root):


    def dfs(root,x):
        if root:
            dfs(root.left, x)
            x+=(root.val)
            dfs(root.right,x)

        return x

    return(sum(dfs(root,x=0)))

任何帮助或指导将不胜感激。

标签： pythonpython-3.xrecursion

Answer 1

x在您的第一个定义中是可变的；每次调用dfs都会引用同一个列表。

在您的第二个示例中，xis immutable。的值x不会被递归调用修改；x += root.val只是更新参数的本地副本。

相反，您需要将 的返回值dfs直接添加到x.

def Sum(root):
    def dfs(root, x):
        if root:
            x += dfs(root.left, x)
            x += root.val
            x += dfs(root.right,x)
        return x

    return dfs(root, x=0)

无需定义dfs，因为您实际上不再进行通用搜索或步行。只需Sum递归调用。还有，返回值就足够了；你根本不需要x争论。

def Sum(root):
    if not root:
        return 0
    else:
        return Sum(root.left) + root.val + Sum(root.right)