时间戳

首页 > 解决方案 > 在递归函数中跟踪和更新值

python - 在递归函数中跟踪和更新值

问题描述

在线找到此代码，可用于在两个叶节点之间的树中查找最大值：

INT_MIN = -2**32

class Node: 
    def __init__(self, data): 
        self.data = data 
        self.left = None
        self.right = None

def maxPathSumUtil(root, res): 
    if root is None: 
        return 0

    if root.left is None and root.right is None: 
        return root.data 

    ls = maxPathSumUtil(root.left, res) 
    rs = maxPathSumUtil(root.right, res) 

    # If both left and right children exist 
    if root.left is not None and root.right is not None:      
        res[0] = max(res[0], ls + rs + root.data) 
        return max(ls, rs) + root.data 

    # If any of the two children is empty, return 
    # root sum for root being on one side 
    if root.left is None: 
        return rs + root.data 
    else: 
        return ls + root.data 

def maxPathSum(root): 
        res = [INT_MIN] 
        maxPathSumUtil(root, res) 
        return res[0]

我的问题是关于res[0]. 为什么要使用只有一个值的列表来跟踪该节点的最大值？我尝试将其更改为常规整数，但没有正确更新。它返回错误的值。那么为什么使用具有单个值的列表而不是使用常规整数来跟踪递归函数期间的最大值呢？

标签： pythonrecursiontree

解决方案

该res列表充当对原始对象的引用，因此即使不返回对象，该函数也可以对其进行变异。

注意：如果您熟悉 C/C++，这就像将引用传递给<type> &<var_name>函数。

以下示例说明了这一点：

>>> def func(ref):
...  ref.append(1)
... 
>>> list_ = [1, 2, 3]
>>> func(list_)
>>> list_
[1, 2, 3, 1]

如图所示，该函数就地更改了对象。

这主要是由于list_和ref指代相同id。

>>> def func(ref):
...  ref.append(1)
...  print('Ref:', id(ref))
... 
>>> list_ = [1, 2, 3]
>>> id(list_)
4421621704
>>> func(list_)
Ref: 4421621704

由于两者list_和都ref引用相同的id，因此对列表的任何更改都将传播到具有相同id's 的其他列表中。

>>> a = [1, 2, 3]
>>> b = a
>>> b.append(10)
>>> id(a), id(b)
(4421619848, 4421619848)
>>> a, b
([1, 2, 3, 10], [1, 2, 3, 10])

请注意a和b具有相同的id，因此它们引用相同的列表对象。这证明了为什么将 a10附加到a.

推荐阅读