### Python 实现二叉树深度计算 #### 深度优先搜索（DFS） 通过递归的方式实现深度优先搜索算法来计算二叉树的最大深度。如果当前节点为空，则返回 0；否则分别递归求解左子树和右子树的高度，取两者较大值并加 1。 以下是基于 DFS 的代码实现： ```python class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right class Solution: def maxDepth(self, root: TreeNode) -> int: if not root: # 如果节点为空 return 0 else: left_height = self.maxDepth(root.left) # 左子树高度 right_height = self.maxDepth(root.right) # 右子树高度 return max(left_height, right_height) + 1 # 当前层高度为左右子树最大高度加1 ``` 此方法的时间复杂度为 O(N)，其中 N 是二叉树中的节点总数，因为每个节点都会被访问一次[^1]。 --- #### 广度优先搜索（BFS） 利用队列逐层遍历二叉树，每处理完一层就增加高度计数器的值。当队列为空时表示已经遍历完整棵树。 下面是 BFS 的具体实现： ```python from collections import deque class Solution: def maxDepth(self, root: TreeNode) -> int: if not root: # 如果根节点为空 return 0 queue = deque([root]) # 初始化队列为根节点 height = 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) height += 1 # 完成一层的遍历，高度加1 return height ``` 该方法同样具有时间复杂度 O(N)[^1]，因为它也需要访问每一个节点恰好一次。 --- ### 结论 无论是采用深度优先还是广度优先的方法都可以有效地解决这个问题。对于较小规模的数据集或者更直观的理解方式来说，推荐使用 **DFS** 方法；而对于大规模数据集以及希望减少栈溢出风险的情况下则更适合选用 **BFS** 方案[^1]。