可以在Python中获取DFS的全局变量以返回正确的值

Question

我正在学习使用Python实施DFS算法。 DFS将在二进制树中返回最大值，

我写了两种方法。第一个方法是Findmax函数 - 它使用返回值来跟踪树中的最大值。第二种方法是FindMax2函数 - 它使用全局变量来跟踪最大值。

我四处搜索，但无法真正理解为什么我的第二种方法不起作用 - 全局变量，max_val，不会返回正确的值，而错误msg是

UnboundLocalError: local variable 'max_val' referenced before
assignment

我在python上不是很好，所以任何帮助非常感谢。 :)这是代码。

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

  def inorder(self, root):
    if root:
      self.inorder(root.left)
      print(root.val)
      self.inorder(root.right)

  def findMax(self, root):
    if root is None:
      return float('-inf')  
    max_lv = self.findMax(root.left)       
    max_rv = self.findMax(root.right)
    return max(root.val, max_lv, max_rv)    

  max_val = float('-inf')
  def findMax_2(self, root):
    if root is None:
      return max_val
    max_val = max(max_val, root.val)    
    dfs(root.left)                      
    dfs(root.right)

r = Node(5)
r.left = Node(1)
r.left.left = Node(8)
r.left.right = Node(11)
r.inorder(r)
print(r.findMax_2(r))

更新： 感谢大家的评论。我根据Ggorlen的建议修改了代码。

def findMax_2(self, root):
    def dfs(node):
      if node is None:
        return max_val
      max_val = max(max_val, node.val)
      print("max_val:", max_val)
      dfs(node.left)
      dfs(node.right)

    max_val = float('-inf')
    dfs(root)
    return max_val

但是我仍然有同样的错误：

Traceback (most recent call last):
  File "dfs_findMax_2.py", line 56, in <module>
    print("max val:", r.findMax_2(r))
  File "dfs_findMax_2.py", line 44, in findMax_2
    dfs(root)
  File "dfs_findMax_2.py", line 38, in dfs
    max_val = max(max_val, node.val)
UnboundLocalError: local variable 'max_val' referenced before assignment

我错过了什么吗？

Answer 1

根据Ggorlen的建议，这是有效的代码。谢谢你！

def findMax_2(self, root):
    def dfs(node):
        nonlocal max_val
        if node is None:
            return
        max_val = max(max_val, node.val)
        dfs(node.left)
        dfs(node.right)

    max_val = float('-inf')
    dfs(root)
    return max_val

Answer 2

Python范围规则有一些尖锐的角落。

在类和外部功能中，max_val是类变量。在函数内部，它是一个词汇变量，该变量范围为函数，恰好具有相同的名称。您的错误是因为您要在分配给词汇变量之前访问词汇变量，因此Python知道您很困惑（但没有给您足够的上下文来毫无意义）。

要访问函数中的类变量，您需要访问self.max_val。

如果它确实是一个全局变量，则需要在函数中使用全局max_val声明。 （不是，所以不要尝试。）对于另一个功能，您需要做一个非局部max_val。

最后，由于它是一个类变量，因此可以通过类的所有实例访问。如果您希望它是实例变量，则将其分配给self.max_val在init方法中，您仍然会通过self.max_val 在其他方法中。