力扣刷题（第二十一天）

灵感来源 

- 保持更新，努力学习

- python脚本学习

二叉树的最大深度

解题思路

这道题要求计算二叉树的最大深度，即从根节点到最远叶子节点的最长路径上的节点数。可以使用递归或迭代方法解决：

1. 递归法（推荐）：

   • 每个节点的最大深度等于其左右子树深度的最大值加 1（当前节点自身）。
   • 递归终止条件：空节点的深度为 0。

     class TreeNode:def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = rightdef maxDepth(root: TreeNode) -> int:if not root:return 0left_depth = maxDepth(root.left)right_depth = maxDepth(root.right)return max(left_depth, right_depth) + 1

2. 迭代法（层序遍历）：

   • 使用队列进行层序遍历（BFS），每遍历一层深度加 1。
   • 每层处理完后，队列中恰好剩下下一层的所有节点。

     from collections import dequeclass TreeNode:def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = rightdef maxDepth(root: TreeNode) -> int:if not root:return 0queue = deque([root])depth = 0while queue:# 当前层的节点数level_size = len(queue)for _ in range(level_size):node = queue.popleft()if node.left:queue.append(node.left)if node.right:queue.append(node.right)depth += 1return depth

逐行解释

递归法

class TreeNode:def __init__(self, val=0, left=None, right=None):self.val = val       # 当前节点的值self.left = left     # 左子节点self.right = right   # 右子节点def maxDepth(root: TreeNode) -> int:# 递归终止条件：如果当前节点为空，深度为0if not root:return 0# 递归计算左子树的最大深度left_depth = maxDepth(root.left)# 递归计算右子树的最大深度right_depth = maxDepth(root.right)# 当前节点的最大深度为左右子树深度的最大值加1（包含当前节点）return max(left_depth, right_depth) + 1

迭代法

from collections import dequeclass TreeNode:def __init__(self, val=0, left=None, right=None):self.val = val       # 当前节点的值self.left = left     # 左子节点self.right = right   # 右子节点def maxDepth(root: TreeNode) -> int:# 如果根节点为空，树的深度为0if not root:return 0# 使用双端队列存储待处理的节点，初始时队列包含根节点queue = deque([root])depth = 0  # 初始化树的深度为0# 循环处理队列中的所有节点，直到队列为空while queue:# 当前层的节点数量（即队列的当前长度）level_size = len(queue)# 处理当前层的所有节点for _ in range(level_size):# 从队列左侧取出一个节点进行处理node = queue.popleft()# 如果该节点有左子节点，将左子节点加入队列if node.left:queue.append(node.left)# 如果该节点有右子节点，将右子节点加入队列if node.right:queue.append(node.right)# 处理完一层后，树的深度加1depth += 1# 返回最终计算的树的最大深度return depth