While solving a leetcode problem (https://leetcode.com/problems/maximum-difference-between-node-and-ancestor), I stumbled upon a strange (and, to me, unexpected) behavior.
A working solution is as follows:
class Solution:
def maxAncestorDiff(self, root: Optional[TreeNode]) -> int:
ancestors = []
max_diff = [0]
def dfs(node):
for v in ancestors:
if abs(v-node.val) > max_diff[0]:
max_diff[0] = abs(v-node.val)
ancestors.append(node.val)
if node.left:
dfs(node.left)
if node.right:
dfs(node.right)
ancestors.pop()
dfs(root)
return max_diff[0]
However, simply modifying the code as follows (making max_diff an int instead of a list):
class Solution:
def maxAncestorDiff(self, root: Optional[TreeNode]) -> int:
ancestors = []
max_diff = 0 # Instead of [0]
def dfs(node):
for v in ancestors:
if abs(v-node.val) > max_diff:
max_diff = abs(v-node.val)
ancestors.append(node.val)
if node.left:
dfs(node.left)
if node.right:
dfs(node.right)
ancestors.pop()
dfs(root)
return max_diff
makes the code execution fail with error:
UnboundLocalError: local variable 'max_diff' referenced before assignment if abs(v-node.val) > max_diff:
My understanding is that max_diff should resolve correctly by looking up 'max_diff' in the outer variable scope (the one of maxAncestorDiff), the same way it does for 'ancestors' and when "max_diff" is a list.
Of course a simple solution to make 'max_diff' an int would be to pass it as an argument to dfs, but I would like to understand why my naive solution does not work. I imagine it's related to the fact that lists are mutable while int are not, but why exactly that makes a difference for scope resolution remains a mystery.
