about PYTHON 3 global variable and change variable in a recursive function, leetcode 104

ENDIF 0
Viewed 15

leetcode 104. Maximum Depth of Binary Tree

My first try is write like this, but the final return value is 0 although in the recursive function depth increased to correct value.

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        
        depth = 0
        
        def mxdp(root,depth):   
            if root:
                depth += 1
            
            print(root.val,depth)
            
            if root.left:
                mxdp(root.left,depth)
            if root.right:
                mxdp(root.right,depth)
        
        mxdp(root,depth)
        print(depth)
        return depth

Then I try to use global variable after read some online article, below is my 2nd version, but it give me an error: name 'depth' is not defined at this line: depth += 1

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        
        depth = 0
        
        def mxdp(root): 
            global depth
            if root:
                depth += 1  
            if root.left:
                mxdp(root.left)
            if root.right:
                mxdp(root.right)
        
        mxdp(root) 
        return depth

Could you please teach me why none of these two ways are not working? How to write correctly? Thanks!

global-variables python-3.x python
1 Answers

For your second example you need to use self.depth or Solution.depth instead of just depth in order to access the depth variable.

Your first example you would need to use the nonlocal keyword in order to update the variable that is out of scope.

def mxdp(root):
    nonlocal depth
    ...

Both of these will still return the incorrect value however because you are adding 1 to the depth at each iteration, and most trees have more than just one branch.

An alternative to both of these approaches which avoids using global or out of scope variables would be to create a separate method that takes the root node and an integer and use the integer to keep track of the depth value, returning that value once you have finally reached the bottom and making sure you keep the largest on your way back out.

For example:

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        return self.recurse(root, 1)
        
    
    def recurse(self, root, depth):
        depth_left = depth_right = 0
        if root.left is None and root.right is None:
            return depth
        if root.left is not None:
            depth_left = self.recurse(root.left, depth + 1)
        if root.right is not None:
            depth_right = self.recurse(root.right, depth + 1)
        return max([depth_left, depth_right])
userphOc10
Related