LeetCode 104二叉树最大深度：递归变量修改问题及正确实现

第一版代码错误原因 #

1. 不可变类型传递问题：Python里整数属于不可变类型，递归函数mxdp里的depth是独立的局部变量，和外层maxDepth方法中的depth完全无关。每次递归传递的是当前depth的副本，修改局部的depth不会影响外层变量，所以最终返回的始终是初始值0。
2. 逻辑漏洞：代码没有记录最大深度，只是单纯累加节点遇到时的depth值，左右子树递归过程中没有比较并保留最大值；另外如果root为None，访问root.val会直接抛出异常。

第二版代码错误原因 #

global depth声明的是模块级全局变量，但你定义的depth是maxDepth方法内部的局部变量，模块全局作用域中根本不存在这个变量，所以执行depth +=1时会报"name 'depth' is not defined"。就算把global改成nonlocal（用于修改外层函数的局部变量），这个逻辑依然有问题——递归进入子节点时累加depth，但回溯时没有减回去，会导致深度计算错误。

正确的实现方式 #

方法1：递归分治（最简洁） #

利用二叉树递归性质：二叉树的最大深度 = 1 + 左、右子树最大深度的较大值，空树深度为0。

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        left_depth = self.maxDepth(root.left)
        right_depth = self.maxDepth(root.right)
        return 1 + max(left_depth, right_depth)

方法2：迭代DFS（栈模拟递归） #

用栈保存节点和对应的深度，遍历过程中记录最大深度：

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        max_depth = 0
        stack = [(root, 1)]
        while stack:
            node, depth = stack.pop()
            max_depth = max(max_depth, depth)
            # 先压右节点，保证左节点先被处理
            if node.right:
                stack.append((node.right, depth + 1))
            if node.left:
                stack.append((node.left, depth + 1))
        return max_depth

方法3：迭代BFS（按层遍历） #

用队列实现层序遍历，每遍历完一层深度加1：

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        max_depth = 0
        from collections import deque
        queue = deque([root])
        while queue:
            level_size = len(queue)
            max_depth += 1
            # 处理当前层所有节点
            for _ in range(level_size):
                node = queue.popleft()
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
        return max_depth

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