如何在python的递归函数中维护全局变量？

Question

无法跟踪变量maxSum，在递归调用后，它会一直重置回0，尽管它在调用中作为参数传递。函数maxPathSum应该返回11，但它返回0

class TreeNode:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def maxPathSum(node):
    sums = []
    maxPath = []
    maxSum = 0
    recursiveSum(node, 0, maxSum, sums)
    return maxSum


def recursiveSum(node, ssum, maxSum, sums):
    if node == None:
        return
    
    if maxSum < ssum + node.val and node.left == None and node.right == None:
        maxSum = ssum + node.val
            
    sums.append(maxSum)
    
    # traverse left subtree
    recursiveSum(node.left, ssum + node.val, maxSum, sums)
    # traverse right subtree
    recursiveSum(node.right, ssum + node.val, maxSum, sums)


root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.right.left = TreeNode(7)
root.right.right = TreeNode(6)
print(maxPathSum(root))

Answer 1

您可以通过以下两种修改之一实现目标

由于从maxSum值构建列表，因此只需更改maxPathSum函数的最后一行即可：

def maxPathSum(node):
    sums = []
    maxPath = []
    maxSum = 0
    recursiveSum(node, 0, maxSum, sums)
    return max(sums)

或者您可以使用maxSum变量，但为此，您必须在两个函数中进行一些小的修改：

def maxPathSum(node):
    sums = []
    maxPath = []
    maxSum = 0
    maxSum=recursiveSum(node, 0, maxSum, sums)
    return maxSum

def recursiveSum(node, ssum, maxSum, sums):
    if node == None:
        return
    
    if maxSum < ssum + node.val and node.left == None and node.right == None:
        maxSum = ssum + node.val
            
    sums.append(maxSum)
    
    # traverse left subtree
    s=recursiveSum(node.left, ssum + node.val, maxSum, sums)
    if s!=None: maxSum=max(maxSum,s)
    # traverse right subtree
    s=recursiveSum(node.right, ssum + node.val, maxSum, sums)
    if s!=None: maxSum=max(maxSum,s)
    return maxSum