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

Question

在网上找到了这段代码，可用于查找树中两个叶节点之间的最大值:

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]。为什么使用只有一个值的列表来跟踪该节点的最大值？我尝试将其更改为常规整数，但它没有正确更新。它返回错误的值。那么，为什么在递归函数期间使用具有单个值的列表比使用常规整数来跟踪最大值更有效呢？

Answer 1

res list 充当原始对象的引用，因此即使不返回该对象，该函数也可以改变它。

_{注意:如果您熟悉 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 的其他列表。的。

>>> 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 ，因此它们引用相同的列表对象。这证明了为什么 10已附加到a .