Python实现二叉树DFS时max_val报UnboundLocalError问题求解

问题描述 #

• 学习目标：使用Python实现DFS算法，返回二叉树中的节点最大值
• 已完成可运行方案：findMax函数，通过函数返回值逐层传递、追踪树中的最大值
• 待排查方案：findMax_2函数，尝试通过变量追踪遍历过程中的最大值，运行始终抛出UnboundLocalError: local variable 'max_val' referenced before assignment错误，查阅资料未定位根因

初始编写代码 #

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))

第一次修改尝试 #

根据建议调整代码结构：在findMax_2内部初始化max_val，通过嵌套的dfs函数执行遍历，修改后代码如下：

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

错误根因 #

报错核心是Python的变量作用域规则：

• 如果在函数内部对某个变量名执行赋值操作，Python默认将该变量识别为当前函数的局部变量，不会自动向外层作用域查找同名变量
• 初始版本代码中，findMax_2内部直接写max_val = max(max_val, root.val)，Python会把max_val当成findMax_2的局部变量，但赋值语句右侧引用max_val时，局部变量还未完成赋值，因此触发报错；同时代码中调用的dfs()函数并未定义，遍历逻辑本身也无法执行
• 修改后的嵌套函数版本中，内层dfs函数内存在max_val的赋值操作，Python同样将max_val识别为dfs的局部变量，赋值前引用就会抛出完全相同的错误

修复方案 #

方案1：嵌套函数+nonlocal声明 #

使用nonlocal关键字明确告诉Python，dfs内的max_val不是局部变量，而是外层findMax_2作用域的变量，修复后代码如下：

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

方案2：使用实例属性存储最大值 #

直接把最大值挂在实例属性self上，避免跨作用域变量的识别问题，修复后完整类方法参考：

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)    

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

# 测试代码
r = Node(5)
r.left = Node(1)
r.left.left = Node(8)
r.left.right = Node(11)
print(r.findMax_2(r))  # 输出11，结果正确

内容的提问来源于stack exchange，提问作者LED Fantom